1 module compy.hal; 2 3 import compy.common; 4 5 import std.algorithm; 6 import std.array; 7 import std.exception; 8 import std.range; 9 import std.traits; 10 debug import std.stdio; 11 12 private static immutable (ubyte[] function(const(ubyte)[] input, const(ubyte)[] buffer, out ushort size) @safe pure nothrow)[] compFuncsV1 = [ &repeatByte, &repeatWord, &zeroFill, &bufferCopy, &bitReverseBufferCopy, &byteReverseBufferCopy ]; 13 private static immutable (ubyte[] function(const(ubyte)[] input, const(ubyte)[] buffer, out ushort size) @safe pure nothrow)[] compFuncsV2 = [ &repeatByte, &repeatWord, &incByteFill, &bufferCopy, &bitReverseBufferCopy, &byteReverseBufferCopy ]; 14 15 private enum BANKSIZE = 0x10000; 16 private enum Command : ubyte { uncompressed = 0, byteFill, shortFill, byteFillIncreasing, zeroFill = byteFillIncreasing, bufferCopy, bitReversedBufferCopy, byteReversedBufferCopy, extend} 17 18 19 ///Older format used in pokemon games 20 struct HALLZ1 { 21 static ubyte[] comp(const(ubyte)[] input) @safe { 22 const(ubyte)[] buffer = input; 23 ubyte[] output, tmpBuffer, tmpBuffer2, uncompBuffer; 24 ushort size, tmpSize, uncompSize; 25 short bufferPos = -1; 26 byte method; 27 float ratio; 28 float tmpRatio; 29 while (input.length > 0) { 30 ratio = 1.0; 31 method = -1; 32 tmpBuffer = []; 33 foreach (k, compFunc; compFuncsV1) { 34 tmpBuffer2 = compFunc(input, buffer[0..bufferPos+1], tmpSize); 35 tmpRatio = cast(float)tmpSize / cast(float)tmpBuffer2.length; 36 debug(verbosecomp) writefln("Method %d: %f", k, tmpRatio); 37 if (tmpRatio > ratio) { 38 debug(verbosecomp) writeln("Candidate found: ", k); 39 method = cast(byte)k; 40 tmpBuffer = tmpBuffer2; 41 ratio = tmpRatio; 42 size = tmpSize; 43 } 44 } 45 if (tmpBuffer.length == 0) { 46 uncompBuffer ~= input[0]; 47 bufferPos++; 48 size = 1; 49 } else { 50 debug(verbosecomp) writeln("Selecting method ", method); 51 bufferPos += tmpBuffer.length; 52 while (uncompBuffer.length > 0) { 53 output ~= uncompdata(uncompBuffer, uncompSize); 54 uncompBuffer = uncompBuffer[uncompSize..$]; 55 } 56 output ~= tmpBuffer; 57 } 58 input = input[size..$]; 59 } 60 while (uncompBuffer.length > 0) { 61 output ~= uncompdata(uncompBuffer, uncompSize); 62 uncompBuffer = uncompBuffer[uncompSize..$]; 63 } 64 debug(verbosecomp) writefln("Compressed size: %d/%d (%0.2f)", output.length + 1, buffer.length, (cast(double)output.length + 1.0) / cast(double)buffer.length * 100.0); 65 return output ~ 0xFF; 66 } 67 static ubyte[] decomp(const(ubyte)[] input) @safe { 68 size_t throwAway; 69 return decomp(input, throwAway); 70 } 71 static ubyte[] decomp(T)(T input, out size_t compressedSize) if (isInputRange!T) { 72 ubyte[] buffer = new ubyte[](BANKSIZE); 73 ubyte commandbyte; 74 Command commandID; 75 ushort commandLength; 76 ushort bufferpos; 77 int decompSize = 0; 78 decompLoop: while(decompSize < BANKSIZE) { //decompressed data cannot exceed 64KB 79 commandbyte = input.readByte(); 80 compressedSize++; 81 commandID = cast(Command)(commandbyte >> 5); 82 if (commandID == Command.extend) { //Extend length of command 83 commandID = cast(Command)((commandbyte & 0x1C) >> 2); 84 if (commandID != Command.extend) { //Double extend does not have a length 85 commandLength = ((commandbyte & 3) << 8) + input.readByte() + 1; 86 compressedSize++; 87 } 88 } else { 89 commandLength = (commandbyte & 0x1F) + 1; 90 } 91 debug(verbosecomp) writeln(commandID, ", ", commandLength); 92 if ((commandID >= Command.bufferCopy) && (commandID < Command.extend)) { //Read buffer position 93 const next = input.readByte(); 94 bufferpos = next >= 0x80 ? cast(ushort)(decompSize - (next & 0x7F) - 1) : ((next << 8) + input.readByte()); 95 debug(verbosecomp) writeln("\t", next, ", ", bufferpos); 96 compressedSize += next > 0x80 ? 1 : 2; 97 } 98 with(Command) final switch(commandID) { 99 case uncompressed: //Following data is uncompressed 100 copy(input.takeExactly(commandLength), buffer[decompSize..decompSize+commandLength]); 101 input.popFrontN(commandLength); 102 compressedSize += commandLength; 103 break; //copy uncompressed data directly into buffer 104 case byteFill: //Fill range with following byte 105 buffer[decompSize..decompSize+commandLength] = input.readByte(); 106 compressedSize++; 107 break; 108 case shortFill: //Fill range with following short 109 (cast(ushort[])buffer[decompSize..decompSize+commandLength*2])[] = cast(ushort)(input.readByte() + (input.readByte() << 8)); 110 compressedSize += 2; 111 break; 112 case zeroFill: //Fill range with zeroes 113 buffer[decompSize..decompSize+commandLength] = 0; 114 break; 115 case bufferCopy: //Copy from buffer 116 copy(buffer[bufferpos..bufferpos+commandLength], buffer[decompSize..decompSize+commandLength]); 117 break; 118 case bitReversedBufferCopy: //Copy from buffer, but with reversed bits 119 copy(buffer[bufferpos..bufferpos+commandLength].map!reversebits, buffer[decompSize..decompSize+commandLength]); 120 break; 121 case byteReversedBufferCopy: //Copy from buffer, but with reversed bytes 122 copy(buffer[bufferpos-commandLength+1..bufferpos+1].retro, buffer[decompSize..decompSize+commandLength]); 123 break; 124 case extend: break decompLoop; 125 } 126 debug(verbosecomp) writefln!"[%(%02X %)]"(buffer[decompSize..decompSize+commandLength]); 127 decompSize += commandLength; 128 } 129 buffer.length = decompSize; 130 return buffer; 131 } 132 } 133 ///Newer format used in later games (Earthbound, Kirby's Super Star) 134 struct HALLZ2 { 135 static ubyte[] comp(const(ubyte)[] input) @safe { 136 const(ubyte)[] buffer = input; 137 ubyte[] output, tmpBuffer, tmpBuffer2, uncompBuffer; 138 ushort size, tmpSize, uncompSize; 139 short bufferPos = -1; 140 byte method; 141 float ratio; 142 float tmpRatio; 143 while (input.length > 0) { 144 ratio = 1.0; 145 method = -1; 146 tmpBuffer = []; 147 foreach (k, compFunc; compFuncsV2) { 148 tmpBuffer2 = compFunc(input, buffer[0..bufferPos+1], tmpSize); 149 tmpRatio = cast(float)tmpSize / cast(float)tmpBuffer2.length; 150 debug(verbosecomp) writefln("Method %d: %f", k, tmpRatio); 151 if (tmpRatio > ratio) { 152 debug(verbosecomp) writeln("Candidate found: ", k); 153 method = cast(byte)k; 154 tmpBuffer = tmpBuffer2; 155 ratio = tmpRatio; 156 size = tmpSize; 157 } 158 } 159 if (tmpBuffer.length == 0) { 160 uncompBuffer ~= input[0]; 161 bufferPos++; 162 size = 1; 163 } else { 164 debug(verbosecomp) writeln("Selecting method ", method); 165 bufferPos += tmpBuffer.length; 166 while (uncompBuffer.length > 0) { 167 output ~= uncompdata(uncompBuffer, uncompSize); 168 uncompBuffer = uncompBuffer[uncompSize..$]; 169 } 170 output ~= tmpBuffer; 171 } 172 input = input[size..$]; 173 } 174 while (uncompBuffer.length > 0) { 175 output ~= uncompdata(uncompBuffer, uncompSize); 176 uncompBuffer = uncompBuffer[uncompSize..$]; 177 } 178 debug(verbosecomp) writefln("Compressed size: %d/%d (%0.2f)", output.length + 1, buffer.length, (cast(double)output.length + 1.0) / cast(double)buffer.length * 100.0); 179 return output ~ 0xFF; 180 } 181 static ubyte[] decomp(const(ubyte)[] input) @safe { 182 size_t throwAway; 183 return decomp(input, throwAway); 184 } 185 static ubyte[] decomp(T)(T input, out size_t compressedSize) if (isInputRange!T) { 186 ubyte[] buffer = new ubyte[](BANKSIZE); 187 ubyte commandbyte = void; 188 Command commandID = void; 189 ushort commandLength = void, bufferpos = void; 190 int decompSize = 0; 191 decompLoop: while(decompSize < BANKSIZE) { //decompressed data cannot exceed 64KB 192 commandbyte = input.readByte(); 193 compressedSize++; 194 commandID = cast(Command)(commandbyte >> 5); 195 if (commandID == Command.extend) { //Extend length of command 196 commandID = cast(Command)((commandbyte & 0x1C) >> 2); 197 if (commandID != Command.extend) { //Double extend does not have a length 198 commandLength = ((commandbyte & 3) << 8) + input.readByte() + 1; 199 compressedSize++; 200 } 201 } else { 202 commandLength = (commandbyte & 0x1F) + 1; 203 } 204 if ((commandID >= Command.bufferCopy) && (commandID < Command.extend)) { //Read buffer position 205 bufferpos = (input.readByte() << 8) + input.readByte(); 206 compressedSize += 2; 207 enforce(bufferpos < BANKSIZE, "Buffer position exceeds bank size!"); 208 enforce(bufferpos < decompSize, "Buffer contents at position unknown!"); 209 } 210 debug(verbosecomp) writeln(commandID, ", ", commandLength, ", ", bufferpos); 211 with(Command) final switch(commandID) { 212 case uncompressed: //Following data is uncompressed 213 buffer[decompSize..decompSize+commandLength] = array(input.takeExactly(commandLength)); 214 input.popFrontN(commandLength); 215 compressedSize += commandLength; 216 break; //copy uncompressed data directly into buffer 217 case byteFill: //Fill range with following byte 218 buffer[decompSize..decompSize+commandLength] = input.readByte(); 219 compressedSize++; 220 break; 221 case shortFill: //Fill range with following short 222 commandLength *= 2; 223 (cast(ushort[])buffer[decompSize..decompSize+commandLength])[] = cast(ushort)(input.readByte() + (input.readByte() << 8)); 224 compressedSize += 2; 225 break; 226 case byteFillIncreasing: //Fill range with increasing byte, beginning with following value 227 buffer[decompSize..decompSize+commandLength] = increaseval(input.readByte(), commandLength); 228 compressedSize++; 229 break; 230 case bufferCopy: //Copy from buffer 231 buffer[decompSize..decompSize+commandLength] = buffer[bufferpos..bufferpos+commandLength]; 232 break; 233 case bitReversedBufferCopy: //Copy from buffer, but with reversed bits 234 copy(buffer[bufferpos..bufferpos+commandLength].map!reversebits, buffer[decompSize..decompSize+commandLength]); 235 break; 236 case byteReversedBufferCopy: //Copy from buffer, but with reversed bytes 237 copy(buffer[bufferpos-commandLength+1..bufferpos+1].retro, buffer[decompSize..decompSize+commandLength]); 238 break; 239 case extend: break decompLoop; 240 } 241 decompSize += commandLength; 242 } 243 buffer.length = decompSize; 244 return buffer; 245 } 246 } 247 @safe unittest { 248 void comptest(ubyte[] input, string msg, int idealsize = -1) @safe { 249 auto data = HALLZ2.comp(input); 250 assert(HALLZ2.decomp(data) == input, "Comp: " ~ msg); 251 //if (idealsize >= 0) 252 // assert(data.length == idealsize, "Comp: " ~ msg ~ " ideal size"); 253 } 254 255 comptest([1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], "Byte-fill Compression"); 256 comptest([1,2,1,2,1,2,1,2,1,2,1,2,1,2], "Word-fill Compression"); 257 comptest([1,2,3,4,5,6,7,8,9,10,11,12,13,14,15], "Increasing Byte-fill Compression"); 258 comptest([1,3,3,3,3,3,7,1,3,3,3,3,3,7,1,3,3,3,3,3,7], "Buffer Compression", 13); 259 comptest([1,3,3,3,3,3,7,7,3,3,3,3,3,1,7,3,3,3,3,3,1], "Reverse Buffer Compression", 13); 260 comptest([1,3,3,3,3,3,7,128,192,192,192,192,192,224,128,192,192,192,192,192,224], "Bit-reversed Buffer Compression", 13); 261 ubyte[] testArray = new ubyte[513]; 262 testArray[] = 1; 263 comptest(testArray, "Extended byte-fill", 4); 264 } 265 266 @safe unittest { 267 assertThrown(HALLZ2.decomp([0x80, 0xFF, 0x00, 0xFF]) == [], "Decomp: Uninitialized buffer"); 268 269 void decomptest(ubyte[] input, ubyte[] output, string msg) { 270 import std.conv : text; 271 size_t finalSize; 272 auto data = HALLZ2.decomp(input, finalSize); 273 assert(data == output, text("Decomp: ", msg, " ", data, " != ", output)); 274 assert(finalSize == input.length, "Decomp: " ~ msg ~ " size"); 275 } 276 decomptest([0x03, 1, 3, 3, 7, 0xFF], [1, 3, 3, 7], "Uncompressed data"); 277 decomptest([0x21, 1, 0xFF], [1, 1], "Byte fill"); 278 decomptest([0x41, 1, 2, 0xFF], [1, 2, 1, 2], "Word fill"); 279 decomptest([0x63, 0, 0xFF], [0, 1, 2, 3], "Decomp: Increasing value"); 280 decomptest([0x61, 1, 0x80, 0, 0, 0xFF], [1, 2, 1], "Buffer copy"); 281 decomptest([0x61, 1, 0xA0, 0, 0, 0xFF], [1, 2, 128], "Bit-reversed Buffer copy"); 282 decomptest([0x61, 1, 0xC1, 0, 1, 0xFF], [1, 2, 2, 1], "Byte-reversed buffer copy"); 283 ubyte[] testArray = new ubyte[513]; 284 testArray[] = 1; 285 decomptest([0xE6, 0, 1, 0xFF], testArray, "Extended byte fill"); 286 }