From 653543541319e2318d2fc572cf5c7f3275b9c12c Mon Sep 17 00:00:00 2001 From: Eugene Kliuchnikov Date: Thu, 24 Aug 2017 13:29:48 +0200 Subject: Update (#589) * cleanup * fix `unbrotli` CLI * Java retouch for faster JS decoder --- c/dec/decode.c | 2 -- c/enc/hash_to_binary_tree_inc.h | 4 ++- c/tools/brotli.c | 2 +- java/org/brotli/dec/BitReader.java | 45 +++++++++++++++++++------------ java/org/brotli/dec/Decode.java | 47 ++++++++++++++++++++++++--------- java/org/brotli/dec/Dictionary.java | 3 +++ java/org/brotli/dec/DictionaryData.java | 16 ++++++----- java/org/brotli/dec/State.java | 1 - 8 files changed, 79 insertions(+), 41 deletions(-) diff --git a/c/dec/decode.c b/c/dec/decode.c index fa5fe48..be8de42 100644 --- a/c/dec/decode.c +++ b/c/dec/decode.c @@ -1260,8 +1260,6 @@ static void BROTLI_NOINLINE WrapRingBuffer(BrotliDecoderState* s) { Last two bytes of ring-buffer are initialized to 0, so context calculation could be done uniformly for the first two and all other positions. - - Custom dictionary, if any, is copied to the end of ring-buffer. */ static BROTLI_BOOL BROTLI_NOINLINE BrotliEnsureRingBuffer( BrotliDecoderState* s) { diff --git a/c/enc/hash_to_binary_tree_inc.h b/c/enc/hash_to_binary_tree_inc.h index 1530c1b..30c71b5 100755 --- a/c/enc/hash_to_binary_tree_inc.h +++ b/c/enc/hash_to_binary_tree_inc.h @@ -20,7 +20,9 @@ #define BUCKET_SIZE (1 << BUCKET_BITS) static BROTLI_INLINE size_t FN(HashTypeLength)(void) { return 4; } -static BROTLI_INLINE size_t FN(StoreLookahead)(void) { return MAX_TREE_COMP_LENGTH; } +static BROTLI_INLINE size_t FN(StoreLookahead)(void) { + return MAX_TREE_COMP_LENGTH; +} static uint32_t FN(HashBytes)(const uint8_t *data) { uint32_t h = BROTLI_UNALIGNED_LOAD32(data) * kHashMul32; diff --git a/c/tools/brotli.c b/c/tools/brotli.c index fe20e0d..557ec93 100755 --- a/c/tools/brotli.c +++ b/c/tools/brotli.c @@ -146,7 +146,7 @@ static Command ParseAlias(const char* name) { size_t unbrotli_len = strlen(unbrotli); name = FileName(name); /* Partial comparison. On Windows there could be ".exe" suffix. */ - if (strncmp(name, unbrotli, unbrotli_len)) { + if (strncmp(name, unbrotli, unbrotli_len) == 0) { char terminator = name[unbrotli_len]; if (terminator == 0 || terminator == '.') return COMMAND_DECOMPRESS; } diff --git a/java/org/brotli/dec/BitReader.java b/java/org/brotli/dec/BitReader.java index 929c7f0..5d54e01 100755 --- a/java/org/brotli/dec/BitReader.java +++ b/java/org/brotli/dec/BitReader.java @@ -43,11 +43,13 @@ final class BitReader { *

After encountering the end of the input stream, 64 additional zero bytes are copied to the * buffer. */ - // TODO: Split to check and read; move read outside of decoding loop. static void readMoreInput(State s) { - if (s.halfOffset <= HALF_WATERLINE) { - return; + if (s.halfOffset > HALF_WATERLINE) { + doReadMoreInput(s); } + } + + static void doReadMoreInput(State s) { if (s.endOfStreamReached != 0) { if (halfAvailable(s) >= -2) { return; @@ -89,6 +91,7 @@ final class BitReader { static void fillBitWindow(State s) { if (s.bitOffset >= HALF_BITNESS) { + // Same as doFillBitWindow. JVM fails to inline it. if (BITNESS == 64) { s.accumulator64 = ((long) s.intBuffer[s.halfOffset++] << HALF_BITNESS) | (s.accumulator64 >>> HALF_BITNESS); @@ -100,6 +103,17 @@ final class BitReader { } } + private static void doFillBitWindow(State s) { + if (BITNESS == 64) { + s.accumulator64 = ((long) s.intBuffer[s.halfOffset++] << HALF_BITNESS) + | (s.accumulator64 >>> HALF_BITNESS); + } else { + s.accumulator32 = ((int) s.shortBuffer[s.halfOffset++] << HALF_BITNESS) + | (s.accumulator32 >>> HALF_BITNESS); + } + s.bitOffset -= HALF_BITNESS; + } + static int peekBits(State s) { if (BITNESS == 64) { return (int) (s.accumulator64 >>> s.bitOffset); @@ -109,7 +123,6 @@ final class BitReader { } static int readFewBits(State s, int n) { - fillBitWindow(s); int val = peekBits(s) & ((1 << n) - 1); s.bitOffset += n; return val; @@ -119,18 +132,16 @@ final class BitReader { if (HALF_BITNESS >= 24) { return readFewBits(s, n); } else { - if (n <= 16) { - return readFewBits(s, n); - } else if (s.bitOffset + n <= BITNESS) { - return readFewBits(s, n); - } else { - int lo = readFewBits(s, 16); - int hi = readFewBits(s, n - 16); - return lo | (hi << 16); - } + return (n <= 16) ? readFewBits(s, n) : readManyBits(s, n); } } + private static int readManyBits(State s, int n) { + int low = readFewBits(s, 16); + doFillBitWindow(s); + return low | (readFewBits(s, n - 16) << 16); + } + static void initBitReader(State s) { s.byteBuffer = new byte[BUFFER_SIZE]; if (BITNESS == 64) { @@ -146,11 +157,11 @@ final class BitReader { prepare(s); } - static void prepare(State s) { + private static void prepare(State s) { readMoreInput(s); checkHealth(s, 0); - fillBitWindow(s); - fillBitWindow(s); + doFillBitWindow(s); + doFillBitWindow(s); } static void reload(State s) { @@ -162,7 +173,7 @@ final class BitReader { static void jumpToByteBoundary(State s) { int padding = (BITNESS - s.bitOffset) & 7; if (padding != 0) { - int paddingBits = readBits(s, padding); + int paddingBits = readFewBits(s, padding); if (paddingBits != 0) { throw new BrotliRuntimeException("Corrupted padding bits"); } diff --git a/java/org/brotli/dec/Decode.java b/java/org/brotli/dec/Decode.java index 4e1e35e..4a1ded6 100755 --- a/java/org/brotli/dec/Decode.java +++ b/java/org/brotli/dec/Decode.java @@ -124,6 +124,7 @@ final class Decode { }; private static int decodeWindowBits(State s) { + BitReader.fillBitWindow(s); if (BitReader.readFewBits(s, 1) == 0) { return 16; } @@ -178,6 +179,7 @@ final class Decode { * Decodes a number in the range [0..255], by reading 1 - 11 bits. */ private static int decodeVarLenUnsignedByte(State s) { + BitReader.fillBitWindow(s); if (BitReader.readFewBits(s, 1) != 0) { int n = BitReader.readFewBits(s, 3); if (n == 0) { @@ -190,6 +192,7 @@ final class Decode { } private static void decodeMetaBlockLength(State s) { + BitReader.fillBitWindow(s); s.inputEnd = BitReader.readFewBits(s, 1); s.metaBlockLength = 0; s.isUncompressed = 0; @@ -208,6 +211,7 @@ final class Decode { return; } for (int i = 0; i < sizeBytes; i++) { + BitReader.fillBitWindow(s); int bits = BitReader.readFewBits(s, 8); if (bits == 0 && i + 1 == sizeBytes && sizeBytes > 1) { throw new BrotliRuntimeException("Exuberant nibble"); @@ -216,6 +220,7 @@ final class Decode { } } else { for (int i = 0; i < sizeNibbles; i++) { + BitReader.fillBitWindow(s); int bits = BitReader.readFewBits(s, 4); if (bits == 0 && i + 1 == sizeNibbles && sizeNibbles > 4) { throw new BrotliRuntimeException("Exuberant nibble"); @@ -252,6 +257,7 @@ final class Decode { BitReader.fillBitWindow(s); int code = readSymbol(table, offset, s); int n = BLOCK_LENGTH_N_BITS[code]; + BitReader.fillBitWindow(s); return BLOCK_LENGTH_OFFSET[code] + BitReader.readBits(s, n); } @@ -325,6 +331,7 @@ final class Decode { repeat -= 2; repeat <<= extraBits; } + BitReader.fillBitWindow(s); repeat += BitReader.readFewBits(s, extraBits) + 3; int repeatDelta = repeat - oldRepeat; if (symbol + repeatDelta > numSymbols) { @@ -363,6 +370,7 @@ final class Decode { BitReader.readMoreInput(s); // TODO: Avoid allocation. int[] codeLengths = new int[alphabetSize]; + BitReader.fillBitWindow(s); simpleCodeOrSkip = BitReader.readFewBits(s, 2); if (simpleCodeOrSkip == 1) { // Read symbols, codes & code lengths directly. int maxBitsCounter = alphabetSize - 1; @@ -376,6 +384,7 @@ final class Decode { // TODO: uncomment when codeLengths is reused. // Utils.fillWithZeroes(codeLengths, 0, alphabetSize); for (int i = 0; i < numSymbols; i++) { + BitReader.fillBitWindow(s); symbols[i] = BitReader.readFewBits(s, maxBits) % alphabetSize; codeLengths[symbols[i]] = 2; } @@ -433,6 +442,7 @@ final class Decode { return numTrees; } + BitReader.fillBitWindow(s); int useRleForZeros = BitReader.readFewBits(s, 1); int maxRunLengthPrefix = 0; if (useRleForZeros != 0) { @@ -448,6 +458,7 @@ final class Decode { contextMap[i] = 0; i++; } else if (code <= maxRunLengthPrefix) { + BitReader.fillBitWindow(s); int reps = (1 << code) + BitReader.readFewBits(s, code); while (reps != 0) { if (i >= contextMapSize) { @@ -462,6 +473,7 @@ final class Decode { i++; } } + BitReader.fillBitWindow(s); if (BitReader.readFewBits(s, 1) == 1) { inverseMoveToFrontTransform(contextMap, contextMapSize); } @@ -590,6 +602,7 @@ final class Decode { s.distanceBlockLength = readMetablockPartition(s, 2, s.numDistanceBlockTypes); BitReader.readMoreInput(s); + BitReader.fillBitWindow(s); s.distancePostfixBits = BitReader.readFewBits(s, 2); s.numDirectDistanceCodes = NUM_DISTANCE_SHORT_CODES + (BitReader.readFewBits(s, 4) << s.distancePostfixBits); @@ -601,6 +614,7 @@ final class Decode { /* Ensure that less than 256 bits read between readMoreInput. */ int limit = Math.min(i + 96, s.numLiteralBlockTypes); for (; i < limit; ++i) { + BitReader.fillBitWindow(s); s.contextModes[i] = (byte) (BitReader.readFewBits(s, 2)); } BitReader.readMoreInput(s); @@ -671,10 +685,6 @@ final class Decode { } private static int writeRingBuffer(State s) { - if (s.bytesToIgnore != 0) { - s.bytesWritten += s.bytesToIgnore; - s.bytesToIgnore = 0; - } int toWrite = Math.min(s.outputLength - s.outputUsed, s.bytesToWrite - s.bytesWritten); if (toWrite != 0) { @@ -752,11 +762,15 @@ final class Decode { s.distanceCode = -1; } int insertCode = INSERT_RANGE_LUT[rangeIdx] + ((cmdCode >>> 3) & 7); + BitReader.fillBitWindow(s); + int insertBits = INSERT_LENGTH_N_BITS[insertCode]; + int insertExtra = BitReader.readBits(s, insertBits); + s.insertLength = INSERT_LENGTH_OFFSET[insertCode] + insertExtra; int copyCode = COPY_RANGE_LUT[rangeIdx] + (cmdCode & 7); - s.insertLength = INSERT_LENGTH_OFFSET[insertCode] + BitReader - .readBits(s, INSERT_LENGTH_N_BITS[insertCode]); - s.copyLength = COPY_LENGTH_OFFSET[copyCode] + BitReader - .readBits(s, COPY_LENGTH_N_BITS[copyCode]); + BitReader.fillBitWindow(s); + int copyBits = COPY_LENGTH_N_BITS[copyCode]; + int copyExtra = BitReader.readBits(s, copyBits); + s.copyLength = COPY_LENGTH_OFFSET[copyCode] + copyExtra; s.j = 0; s.runningState = INSERT_LOOP; @@ -833,8 +847,10 @@ final class Decode { s.distanceCode >>>= s.distancePostfixBits; int n = (s.distanceCode >>> 1) + 1; int offset = ((2 + (s.distanceCode & 1)) << n) - 4; + BitReader.fillBitWindow(s); + int distanceExtra = BitReader.readBits(s, n); s.distanceCode = s.numDirectDistanceCodes + postfix - + ((offset + BitReader.readBits(s, n)) << s.distancePostfixBits); + + ((offset + distanceExtra) << s.distancePostfixBits); } } @@ -873,9 +889,15 @@ final class Decode { int src = (s.pos - s.distance) & ringBufferMask; int dst = s.pos; int copyLength = s.copyLength - s.j; - if ((src + copyLength < ringBufferMask) && (dst + copyLength < ringBufferMask)) { - for (int k = 0; k < copyLength; ++k) { - ringBuffer[dst++] = ringBuffer[src++]; + int srcEnd = src + copyLength; + int dstEnd = dst + copyLength; + if ((srcEnd < ringBufferMask) && (dstEnd < ringBufferMask)) { + if (copyLength < 12 || (srcEnd > dst && dstEnd > src)) { + for (int k = 0; k < copyLength; ++k) { + ringBuffer[dst++] = ringBuffer[src++]; + } + } else { + Utils.copyBytesWithin(ringBuffer, dst, src, srcEnd); } s.j += copyLength; s.metaBlockLength -= copyLength; @@ -941,6 +963,7 @@ final class Decode { while (s.metaBlockLength > 0) { BitReader.readMoreInput(s); // Optimize + BitReader.fillBitWindow(s); BitReader.readFewBits(s, 8); s.metaBlockLength--; } diff --git a/java/org/brotli/dec/Dictionary.java b/java/org/brotli/dec/Dictionary.java index c40f28b..a6867b7 100755 --- a/java/org/brotli/dec/Dictionary.java +++ b/java/org/brotli/dec/Dictionary.java @@ -35,6 +35,9 @@ public final class Dictionary { } public static void setData(ByteBuffer data) { + if (!data.isDirect() || !data.isReadOnly()) { + throw new BrotliRuntimeException("data must be a direct read-only byte buffer"); + } Dictionary.data = data; } diff --git a/java/org/brotli/dec/DictionaryData.java b/java/org/brotli/dec/DictionaryData.java index b7acebe..9ac6e55 100755 --- a/java/org/brotli/dec/DictionaryData.java +++ b/java/org/brotli/dec/DictionaryData.java @@ -19,18 +19,20 @@ final class DictionaryData { private static final String SKIP_FLIP = "\u06F7%\u018C'T%\u0085'W%\u00D7%O%g%\u00A6&\u0193%\u01E5&>&*&'&^&\u0088\u0178\u0C3E&\u01AD&\u0192&)&^&%&'&\u0082&P&1&\u00B1&3&]&m&u&E&t&C&\u00CF&V&V&/&>&6&\u0F76\u177Co&p&@&E&M&P&x&@&F&e&\u00CC&7&:&(&D&0&C&)&.&F&-&1&(&L&F&1\u025E*\u03EA\u21F3&\u1372&K&;&)&E&H&P&0&?&9&V&\u0081&-&v&a&,&E&)&?&=&'&'&B&\u0D2E&\u0503&\u0316*&*8&%&%&&&%,)&\u009A&>&\u0086&7&]&F&2&>&J&6&n&2&%&?&\u008E&2&6&J&g&-&0&,&*&J&*&O&)&6&(&<&B&N&.&P&@&2&.&W&M&%\u053C\u0084(,(<&,&\u03DA&\u18C7&-&,(%&(&%&(\u013B0&X&D&\u0081&j&'&J&(&.&B&3&Z&R&h&3&E&E&<\u00C6-\u0360\u1EF3&%8?&@&,&Z&@&0&J&,&^&x&_&6&C&6&C\u072C\u2A25&f&-&-&-&-&,&J&2&8&z&8&C&Y&8&-&d&\u1E78\u00CC-&7&1&F&7&t&W&7&I&.&.&^&=\u0F9C\u19D3&8(>&/&/&\u077B')'\u1065')'%@/&0&%\u043E\u09C0*&*@&C\u053D\u05D4\u0274\u05EB4\u0DD7\u071A\u04D16\u0D84&/\u0178\u0303Z&*%\u0246\u03FF&\u0134&1\u00A8\u04B4\u0174"; private static void unpackDictionaryData( - byte[] dictionary, String data0, String data1, String skipFlip) { + ByteBuffer dictionary, String data0, String data1, String skipFlip) { int n0 = data0.length(); int n1 = data1.length(); - if (n0 + n1 != dictionary.length) { + if (n0 + n1 != dictionary.capacity()) { throw new RuntimeException("Corrupted brotli dictionary"); } int offset = 0; for (int i = 0; i < n0; ++i) { - dictionary[offset++] = (byte) data0.charAt(i); + dictionary.put(offset, (byte) data0.charAt(i)); + offset++; } for (int i = 0; i < n1; ++i) { - dictionary[offset++] = (byte) data1.charAt(i); + dictionary.put(offset, (byte) data1.charAt(i)); + offset++; } offset = 0; int n = skipFlip.length(); @@ -39,15 +41,15 @@ final class DictionaryData { int flip = skipFlip.charAt(i + 1) - 36; offset += skip; for (int j = 0; j < flip; ++j) { - dictionary[offset] = (byte) (dictionary[offset] | 0x80); + dictionary.put(offset, (byte) (dictionary.get(offset) | 0x80)); offset++; } } } static { - byte[] dictionary = new byte[122784]; + ByteBuffer dictionary = ByteBuffer.allocateDirect(122784); unpackDictionaryData(dictionary, DATA0, DATA1, SKIP_FLIP); - Dictionary.setData(ByteBuffer.wrap(dictionary).asReadOnlyBuffer()); + Dictionary.setData(dictionary.asReadOnlyBuffer()); } } diff --git a/java/org/brotli/dec/State.java b/java/org/brotli/dec/State.java index 47ab84d..183df44 100755 --- a/java/org/brotli/dec/State.java +++ b/java/org/brotli/dec/State.java @@ -68,7 +68,6 @@ final class State { int maxRingBufferSize; int ringBufferSize; int expectedTotalSize; - int bytesToIgnore; int outputOffset; int outputLength; int outputUsed; -- cgit v1.1