1 module lz4; 2 /** 3 * CTFEable LZ4 decompressor 4 * Copyright © 2016 Stefan Koch 5 * All rights reserved 6 */ 7 enum Endianess 8 { 9 BigEndian, 10 LittleEndian 11 } 12 /// JUST TO DEMONSTRATE THAT IT IS UNLIKELY :) 13 auto unlikely(T)(T expressionValue) 14 { 15 return expressionValue; 16 } 17 18 T fromBytes(T, Endianess endianess = Endianess.LittleEndian)(const ubyte[] _data) 19 { 20 static assert(is(T : long)); // poor man's isIntegral 21 T result; 22 23 foreach (i; 0 .. T.sizeof) 24 { 25 static if (endianess == Endianess.LittleEndian) 26 { 27 result |= (_data[i] << i * 8); 28 } 29 else 30 { 31 result |= (_data[i] << (T.sizeof - 1 - i) * 8); 32 } 33 } 34 return result; 35 } 36 37 struct LZ4Header 38 { 39 //TODO: finish this! ("parsing" LZ4 Frame format header) 40 int end = 7; 41 ubyte flags; 42 43 bool hasBlockIndependence; 44 bool hasBlockChecksum; 45 bool hasContentChecksum; 46 47 ulong contentSize; 48 49 this(const ubyte[] data) pure 50 { 51 assert(((data[0] >> 6) & 0b11) == 0b01, "Format can not be read"); 52 53 hasBlockIndependence = ((data[0] >> 5) & 0b1); 54 hasBlockChecksum = ((data[0] >> 4) & 0b1); 55 56 bool hasContentSize = ((data[0] >> 3) & 0b1); 57 58 hasContentChecksum = ((data[0] >> 2) & 0b1); 59 60 if (hasContentSize) 61 { 62 contentSize = fromBytes!ulong(data[2 .. 9]); 63 assert(contentSize); 64 end = 11; 65 } 66 } 67 } 68 69 ubyte[] decodeLZ4File(const ubyte[] data) 70 { 71 assert(data[0 .. 4] == [0x04, 0x22, 0x4d, 0x18], "not a valid LZ4 file"); 72 auto lz4Header = LZ4Header(data[5 .. $]); 73 uint length = fromBytes!uint(data[lz4Header.end .. lz4Header.end + uint.sizeof]); 74 75 return decodeLZ4(data[lz4Header.end + uint.sizeof .. $], length); 76 } 77 78 ubyte[] decodeLZ4(const ubyte[] input, uint blockLength) pure 79 { 80 uint coffset; 81 ubyte[] output; 82 83 while (true) 84 { 85 auto bitfield = input[coffset++]; 86 auto highBits = (bitfield >> 4); 87 auto lowBits = bitfield & 0xF; 88 89 if (highBits) 90 { 91 uint literalsLength = 0xF; 92 93 if (highBits != 0xF) 94 { 95 literalsLength = highBits; 96 } 97 else 98 { 99 while (input[coffset++] == 0xFF) 100 { 101 literalsLength += 0xFF; 102 } 103 literalsLength += input[coffset - 1]; 104 } 105 106 output ~= input[coffset .. coffset + literalsLength]; 107 coffset += literalsLength; 108 } 109 110 if (coffset >= blockLength) 111 return output; 112 113 uint matchLength = 0xF + 4; 114 ushort offset = (input[coffset++] | (input[coffset++] << 8)); 115 116 if (lowBits != 0xF) 117 { 118 matchLength = lowBits + 4; 119 } 120 else 121 { 122 while (input[coffset++] == 0xFF) 123 { 124 matchLength += 0xFF; 125 } 126 matchLength += input[coffset - 1]; 127 } 128 129 if (unlikely(offset < matchLength)) 130 { 131 uint startMatch = cast(uint) output.length - offset; 132 133 // this works for now. Maybe it's even more complicated... 134 // e.g. lz4 widens the offset as the match gets longer 135 // but the docs seem to suggest that the following code is indeed correct 136 137 while (unlikely(offset < matchLength)) 138 { // TODO: IS IT REALLY _unlikely_ or could be _likely_ ? 139 output ~= output[startMatch .. startMatch + offset]; 140 matchLength -= offset; 141 } 142 143 output ~= output[startMatch .. startMatch + matchLength]; 144 } 145 else 146 { 147 output ~= output[$ - offset .. ($ - offset) + matchLength]; 148 } 149 150 } 151 }