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