1 module varint;
2 import utils;
3 
4 //          Copyright Stefan Koch 2015 - 2018.
5 // Distributed under the Boost Software License, Version 1.0.
6 //    (See accompanying file LICENSE.md or copy at
7 //          http://www.boost.org/LICENSE_1_0.txt)
8 
9 enum unrolled = true;
10 
11 struct VarInt
12 {
13 pure nothrow @safe @nogc:
14     this(BigEndian!long value) @trusted
15     {
16         //FIXME the constructor does not work for value bigger then uint.max;
17         auto len = lengthInVarInt(value);
18         long beValue = value.asBigEndian;
19 
20         auto _len = len;
21         while (_len--)
22         {
23             _storage.ptr[_len] = (beValue & 0x7f) | 0x80;
24             beValue >>= 7;
25         }
26         _storage.ptr[len - 1] &= 0x7f;
27 
28         byteArray = _storage[0 .. len];
29     }
30 
31     const ubyte[] byteArray;
32     ubyte[9] _storage;
33     alias toBeLong this;
34 
35     //TODO FIXME toBeLong does not correctly convert negative Numbers
36 
37     @property BigEndian!long toBeLong() @trusted
38     {
39         long tmp;
40         static if (unrolled)
41         {
42             uint v3 = 0;
43 
44             if (byteArray.ptr[0] & 0x80)
45             {
46                 v3 = 1;
47                 if (byteArray.ptr[1] & 0x80)
48                 {
49                     v3 = 2;
50                     if (byteArray.ptr[2] & 0x80)
51                     {
52                         v3 = 3;
53                         if (byteArray.ptr[3] & 0x80)
54                         {
55                             v3 = 4;
56                             if (byteArray.ptr[4] & 0x80)
57                             {
58                                 v3 = 5;
59                                 if (byteArray.ptr[5] & 0x80)
60                                 {
61                                     v3 = 6;
62                                     if (byteArray.ptr[6] & 0x80)
63                                     {
64                                         v3 = 7;
65                                         if (byteArray.ptr[7] & 0x80)
66                                             v3 = 8;
67                                     }
68                                 }
69                             }
70                         }
71                     }
72                 }
73             }
74             else
75             {
76                 BigEndian!long result;
77 
78                 version (LittleEndian)
79                 {
80                     result.asNative = (cast(long) byteArray.ptr[0] << 56);
81                 }
82                 else
83                 {
84                     result.asNative = (cast(long) byteArray.ptr[0]);
85                 }
86                 return result;
87             }
88 
89         }
90         else
91         {
92             uint length = length();
93         }
94 
95         BigEndian!long result;
96 
97         // The hottest loop in the whole program!
98         //TODO There must be a way to speed it up!
99         static if (unrolled)
100         {
101             switch (v3)
102             {
103             case 8:
104                 tmp |= ((cast(long) byteArray.ptr[8]) << 7 * (v3 - 8));
105                 goto case 7;
106             case 7:
107                 tmp |= ((cast(long) byteArray.ptr[7] & 0x7FUL) << 7 * (v3 - 7));
108                 goto case 6;
109             case 6:
110                 tmp |= ((cast(long) byteArray.ptr[6] & 0x7FUL) << 7 * (v3 - 6));
111                 goto case 5;
112             case 5:
113                 tmp |= ((cast(long) byteArray.ptr[5] & 0x7FUL) << 7 * (v3 - 5));
114                 goto case 4;
115             case 4:
116                 tmp |= ((cast(long) byteArray.ptr[4] & 0x7FUL) << 7 * (v3 - 4));
117                 goto case 3;
118             case 3:
119                 tmp |= ((cast(long) byteArray.ptr[3] & 0x7FUL) << 7 * (v3 - 3));
120                 goto case 2;
121             case 2:
122                 tmp |= ((cast(long) byteArray.ptr[2] & 0x7FUL) << 7 * (v3 - 2));
123                 goto case 1;
124             case 1:
125                 tmp |= ((cast(long) byteArray.ptr[1] & 0x7FUL) << 7 * (v3 - 1));
126                 tmp |= ((cast(long) byteArray.ptr[0] & 0x7FUL) << 7 * (v3 - 0));
127                 break;
128             default:
129                 assert(0);
130 
131             }
132         }
133         else
134 
135         {
136             foreach (idx; 0 .. length)
137             {
138                 ubyte val = byteArray[idx];
139                 long maskedVal = (cast(long) val & 0x7fUL); // mask 8th bit
140                 long shiftBy = (length - idx - 1UL) * 7UL;
141                 if (idx < 8)
142                 {
143                     tmp |= (maskedVal << shiftBy);
144                 }
145                 else
146                 {
147                     tmp |= (cast(long) val << 63UL);
148                 }
149             }
150         }
151         //this evokes swapIfNeeded
152         result = tmp;
153 
154         return result;
155     }
156 
157     this(const ubyte[] _arr)
158     {
159         this.byteArray = _arr;
160     }
161 
162     static int lengthInVarInt(BigEndian!long value)
163     {
164         if (value > 1L << 56 || value < 0)
165         {
166             return 9;
167         }
168         else if (value < 1 << 7)
169         {
170             return 1;
171         }
172         else if (value < 1 << 14)
173         {
174             return 2;
175         }
176         else if (value < 1 << 21)
177         {
178             return 3;
179         }
180         else if (value < 1 << 28)
181         {
182             return 4;
183         }
184         else if (value < 1L << 35)
185         {
186             return 5;
187         }
188         else if (value < 1L << 42)
189         {
190             return 6;
191         }
192         else if (value < 1L << 49)
193         {
194             return 7;
195         }
196         else if (value < 1L << 56)
197         {
198             return 8;
199         }
200         assert(0, "We should never get here");
201     }
202 
203     @property uint length()
204     {
205         return _length(byteArray);
206     }
207 
208     static uint _length(const ubyte[] arr)
209     {
210 
211         foreach (idx; 0 .. 9)
212         {
213             if (arr[idx] & (1 << 7))
214             {
215                 continue;
216             }
217             else
218             {
219                 return idx + 1;
220             }
221             assert(0, "we should never get here");
222         }
223         return 9;
224     }
225 
226     static assert(_length((cast(ubyte[])[0x6d, 0x00])) == 1);
227     static assert(_length((cast(ubyte[])[0x7f, 0x00])) == 1);
228     static assert(_length((cast(ubyte[])[0x82, 0x12])) == 2);
229     static assert(_length((cast(ubyte[])[0xfe, 0xfe, 0x00])) == 3);
230     static assert(VarInt((cast(ubyte[])[0x81, 0x01])).toBeLong == 129);
231     static assert(VarInt((cast(ubyte[])[0x81, 0x00])).toBeLong == 0x0080);
232     static assert(VarInt((cast(ubyte[])[0x82, 0x00])).toBeLong == 0x0100); // should be 0x0100
233     static assert(_length((cast(ubyte[])[0x82, 0x80, 0x00])) == 3);
234     static assert(VarInt((cast(ubyte[])[0x84, 0x60, 0x00])).toBeLong == 608);
235     //FIXME make this work!
236     //	static assert(VarInt(cast(ubyte[])[0xFF, 0xFF, 0xFF, 0XFF, 0xFF, 0XFF, 0xFF, 0xFF, 0xEA]).toBeLong == -22);
237     static assert(VarInt(bigEndian!long(265)).toBeLong == 265);
238     static assert(VarInt(bigEndian!long(6421)).toBeLong == 6421);
239     static assert(VarInt(bigEndian!long(22)).toBeLong == 22);
240     static assert(VarInt.lengthInVarInt(BigEndian!long(-22)) == 9);
241     static assert(VarInt(bigEndian!long(uint.max)).toBeLong == uint.max);
242     static assert(VarInt(cast(ubyte[])[0xFF, 0xFF, 0xFF, 0XFF, 0xFF, 0XFF,
243         0xFF, 0xFF, 0xEA]) == VarInt(bigEndian(-22L)));
244     //static assert (VarInt().lengthInVarInt(608) == 2);
245     static assert(VarInt((cast(ubyte[])[0x81, 0x82, 0x83, 0x84, 0x85, 0x86, 0x87, 0x88,
246         0x89])).toBeLong != 0);
247 }