1 /// \file LEB128.d 2 3 module tagion.betterC.utils.LEB128; 4 5 @nogc: 6 7 import std.format; 8 import traits = std.traits : isIntegral, isSigned, isUnsigned; 9 import std.typecons; 10 11 //import tagion.basic.tagionexceptions; 12 import std.algorithm.comparison : min; 13 import std.algorithm.iteration : map, sum; 14 import tagion.betterC.utils.Bailout; 15 import tagion.betterC.utils.BinBuffer; 16 17 //import std.stdio; 18 19 // @safe 20 // class LEB128Exception : TagionException { 21 // this(string msg, string file = __FILE__, size_t line = __LINE__ ) pure { 22 // super( msg, file, line ); 23 // } 24 // } 25 26 // alias check=Check!LEB128Exception; 27 28 size_t calc_size(const(ubyte[]) data) { 29 foreach (i, d; data) { 30 if ((d & 0x80) == 0) { 31 //check(i <= ulong.sizeof+1, "LEB128 overflow"); 32 return i + 1; 33 } 34 } 35 // check(0, "LEB128 bad format"); 36 assert(0); 37 } 38 39 @safe 40 size_t calc_size(T)(const T v) pure if (isUnsigned!(T)) { 41 size_t result; 42 ulong value = v; 43 do { 44 result++; 45 value >>= 7; 46 } 47 while (value); 48 return result; 49 } 50 51 @safe 52 size_t calc_size(T)(const T v) pure if (isSigned!(T)) { 53 if (v == T.min) { 54 return T.sizeof + (is(T == int) ? 1 : 2); 55 } 56 ulong value = ulong((v < 0) ? -v : v); 57 static if (is(T == long)) { 58 if ((value >> (long.sizeof * 8 - 2)) == 1UL) { 59 return long.sizeof + 2; 60 } 61 } 62 size_t result; 63 // auto uv=(v < 0)?-v:v; 64 // T nv=-v; 65 66 ubyte d; 67 do { 68 d = value & 0x7f; 69 result++; 70 value >>= 7; 71 } 72 while ((((value != 0) || (d & 0x40)) && ((value != -1) || !(d & 0x40)))); 73 return result; 74 } 75 76 void encode(T)(ref BinBuffer buffer, const T v) if (isUnsigned!T && isIntegral!T) { 77 ubyte[T.sizeof + 2] data; 78 alias BaseT = TypedefType!T; 79 BaseT value = cast(BaseT) v; 80 foreach (i, ref d; data) { 81 d = value & 0x7f; 82 value >>= 7; 83 if (value == 0) { 84 buffer.write(data[0 .. i + 1]); 85 return; 86 } 87 d |= 0x80; 88 } 89 assert(0); 90 } 91 92 void encode(T)(ref BinBuffer buffer, const T v) if (isSigned!T && isIntegral!T) { 93 enum DATA_SIZE = (T.sizeof * 9 + 1) / 8 + 1; 94 ubyte[DATA_SIZE] data; 95 // size_t index; 96 if (v == T.min) { 97 foreach (ref d; data[0 .. $ - 1]) { 98 d = 0x80; 99 } 100 data[$ - 1] = (T.min >> (7 * (DATA_SIZE - 1))) & 0x7F; 101 buffer.write(data); 102 return; 103 } 104 T value = v; 105 foreach (i, ref d; data) { 106 d = value & 0x7f; 107 value >>= 7; 108 /* sign bit of byte is second high order bit (0x40) */ 109 if (((value == 0) && !(d & 0x40)) || ((value == -1) && (d & 0x40))) { 110 buffer.write(data[0 .. i + 1]); 111 return; 112 } 113 d |= 0x80; 114 } 115 // check(0, "Bad LEB128 format"); 116 assert(0); 117 } 118 119 alias DecodeLEB128(T) = Tuple!(T, "value", size_t, "size"); 120 121 DecodeLEB128!T decode(T = ulong)(const(ubyte[]) data) if (isUnsigned!T) { 122 alias BaseT = TypedefType!T; 123 ulong result; 124 uint shift; 125 enum MAX_LIMIT = T.sizeof * 8; 126 size_t len; 127 foreach (i, d; data) { 128 // check(shift < MAX_LIMIT, 129 // message("LEB128 decoding buffer over limit of %d %d", MAX_LIMIT, shift)); 130 131 result |= (d & 0x7FUL) << shift; 132 if ((d & 0x80) == 0) { 133 len = i + 1; 134 static if (!is(BaseT == ulong)) { 135 check(result <= BaseT.max, message("LEB128 decoding overflow of %x for %s", result, T 136 .stringof)); 137 } 138 return DecodeLEB128!T(cast(BaseT) result, len); 139 } 140 shift += 7; 141 } 142 // check(0, message("Bad LEB128 format for type %s", T.stringof)); 143 assert(0); 144 } 145 146 DecodeLEB128!T decode(T = long)(const(ubyte[]) data) if (isSigned!T) { 147 alias BaseT = TypedefType!T; 148 long result; 149 uint shift; 150 enum MAX_LIMIT = T.sizeof * 8; 151 size_t len; 152 foreach (i, d; data) { 153 // check(shift < MAX_LIMIT, "LEB128 decoding buffer over limit"); 154 result |= (d & 0x7FL) << shift; 155 shift += 7; 156 if ((d & 0x80) == 0) { 157 if ((shift < long.sizeof * 8) && ((d & 0x40) != 0)) { 158 result |= (~0L << shift); 159 } 160 len = i + 1; 161 // static if (!is(BaseT==long)) { 162 // // check((T.min <= result) && (result <= T.max), 163 // // message("LEB128 out of range %d for %s", result, T.stringof)); 164 // } 165 return DecodeLEB128!T(cast(BaseT) result, len); 166 } 167 } 168 // check(0, message("Bad LEB128 format for type %s", T.stringof)); 169 assert(0); 170 } 171 172 /// 173 unittest { 174 import std.algorithm.comparison : equal; 175 176 void ok(T)(T x, const(ubyte[]) expected) { 177 BinBuffer encoded; 178 encode(encoded, x); 179 assert(equal(encoded.serialize, expected)); 180 assert(calc_size(x) == expected.length); 181 assert(calc_size(expected) == expected.length); 182 const decoded = decode!T(expected); 183 assert(decoded.size == expected.length); 184 assert(decoded.value == x); 185 } 186 187 { 188 189 const(ubyte[5]) buffer_0 = [255, 255, 255, 255, 7]; 190 ok!int(int.max, buffer_0); 191 const(ubyte[1]) buffer_1 = [27]; 192 ok!ulong(27, buffer_1); 193 const(ubyte[2]) buffer_2 = [167, 21]; 194 ok!ulong(2727, buffer_2); 195 const(ubyte[3]) buffer_3 = [215, 210, 16]; 196 ok!ulong(272727, buffer_3); 197 const(ubyte[4]) buffer_4 = [151, 204, 128, 13]; 198 ok!ulong(27272727, buffer_4); 199 const(ubyte[5]) buffer_5 = [181, 202, 212, 168, 5]; 200 ok!ulong(1427449141, buffer_5); 201 const(ubyte[10]) buffer_6 = [ 202 255, 255, 255, 255, 255, 255, 255, 255, 255, 1 203 ]; 204 ok!ulong(ulong.max, buffer_6); 205 } 206 207 { 208 const(ubyte[1]) buffer_0 = [127]; 209 ok!int(-1, buffer_0); 210 const(ubyte[5]) buffer_1 = [255, 255, 255, 255, 7]; 211 ok!int(int.max, buffer_1); 212 const(ubyte[5]) buffer_2 = [128, 128, 128, 128, 120]; 213 ok!int(int.min, buffer_2); 214 const(ubyte[5]) buffer_3 = [255, 255, 255, 255, 7]; 215 ok!int(int.max, buffer_3); 216 const(ubyte[5]) buffer_4 = [128, 128, 128, 128, 120]; 217 ok!long(int.min, buffer_4); 218 const(ubyte[5]) buffer_5 = [255, 255, 255, 255, 7]; 219 ok!long(int.max, buffer_5); 220 221 const(ubyte[1]) buffer_6 = [27]; 222 ok!long(27, buffer_6); 223 const(ubyte[2]) buffer_7 = [167, 21]; 224 ok!long(2727, buffer_7); 225 const(ubyte[3]) buffer_8 = [215, 210, 16]; 226 ok!long(272727, buffer_8); 227 const(ubyte[4]) buffer_9 = [151, 204, 128, 13]; 228 ok!long(27272727, buffer_9); 229 230 const(ubyte[5]) buffer_10 = [181, 202, 212, 168, 5]; 231 ok!long(1427449141, buffer_10); 232 233 const(ubyte[3]) buffer_11 = [192, 187, 120]; 234 ok!int(-123456, buffer_11); 235 236 const(ubyte[1]) buffer_12 = [101]; 237 ok!long(-27, buffer_12); 238 const(ubyte[2]) buffer_13 = [217, 106]; 239 ok!long(-2727, buffer_13); 240 const(ubyte[3]) buffer_14 = [169, 173, 111]; 241 ok!long(-272727, buffer_14); 242 const(ubyte[4]) buffer_15 = [233, 179, 255, 114]; 243 ok!long(-27272727, buffer_15); 244 const(ubyte[5]) buffer_16 = [203, 181, 171, 215, 122]; 245 ok!long(-1427449141L, buffer_16); 246 247 const(ubyte[1]) buffer_17 = [127]; 248 ok!long(-1L, buffer_17); 249 250 const(ubyte[10]) buffer_18 = [ 251 254, 255, 255, 255, 255, 255, 255, 255, 255, 0 252 ]; 253 ok!long(long.max - 1, buffer_18); 254 const(ubyte[10]) buffer_19 = [ 255 255, 255, 255, 255, 255, 255, 255, 255, 255, 0 256 ]; 257 ok!long(long.max, buffer_19); 258 const(ubyte[10]) buffer_20 = [ 259 129, 128, 128, 128, 128, 128, 128, 128, 128, 127 260 ]; 261 ok!long(long.min + 1, buffer_20); 262 const(ubyte[10]) buffer_21 = [ 263 128, 128, 128, 128, 128, 128, 128, 128, 128, 127 264 ]; 265 ok!long(long.min, buffer_21); 266 } 267 268 { // Bug fix 269 assert(calc_size(-77) == 2); 270 const(ubyte[2]) buffer_22 = [179, 127]; 271 ok!int(-77, buffer_22); 272 } 273 274 }