Transform.java
/* Copyright 2015 Google Inc. All Rights Reserved.
Distributed under MIT license.
See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
*/
package org.brotli.dec;
import java.nio.ByteBuffer;
/**
* Transformations on dictionary words.
*
* Transform descriptor is a triplet: {prefix, operator, suffix}.
* "prefix" and "suffix" are short strings inserted before and after transformed dictionary word.
* "operator" is applied to dictionary word itself.
*
* Some operators has "built-in" parameters, i.e. parameter is defined by operator ordinal. Other
* operators have "external" parameters, supplied via additional table encoded in shared dictionary.
*
* Operators:
* - IDENTITY (0): dictionary word is inserted "as is"
* - OMIT_LAST_N (1 - 9): last N octets of dictionary word are not inserted; N == ordinal
* - OMIT_FIRST_M (12-20): first M octets of dictionary word are not inserted; M == ordinal - 11
* - UPPERCASE_FIRST (10): first "scalar" is XOR'ed with number 32
* - UPPERCASE_ALL (11): all "scalars" are XOR'ed with number 32
* - SHIFT_FIRST (21): first "scalar" is shifted by number form parameter table
* - SHIFT_ALL (22): all "scalar" is shifted by number form parameter table
*
* Here "scalar" is a variable length character coding similar to UTF-8 encoding.
* UPPERCASE_XXX / SHIFT_XXX operators were designed to change the case of UTF-8 encoded characters.
* While UPPERCASE_XXX works well only on ASCII charset, SHIFT is much more generic and could be
* used for most (all?) alphabets.
*/
final class Transform {
static final class Transforms {
final int numTransforms;
final int[] triplets;
final byte[] prefixSuffixStorage;
final int[] prefixSuffixHeads;
final short[] params;
Transforms(int numTransforms, int prefixSuffixLen, int prefixSuffixCount) {
this.numTransforms = numTransforms;
this.triplets = new int[numTransforms * 3];
this.params = new short[numTransforms];
this.prefixSuffixStorage = new byte[prefixSuffixLen];
this.prefixSuffixHeads = new int[prefixSuffixCount + 1];
}
}
static final int NUM_RFC_TRANSFORMS = 121;
static final Transforms RFC_TRANSFORMS = new Transforms(NUM_RFC_TRANSFORMS, 167, 50);
private static final int OMIT_FIRST_LAST_LIMIT = 9;
private static final int IDENTITY = 0;
private static final int OMIT_LAST_BASE = IDENTITY + 1 - 1; // there is no OMIT_LAST_0.
private static final int UPPERCASE_FIRST = OMIT_LAST_BASE + OMIT_FIRST_LAST_LIMIT + 1;
private static final int UPPERCASE_ALL = UPPERCASE_FIRST + 1;
private static final int OMIT_FIRST_BASE = UPPERCASE_ALL + 1 - 1; // there is no OMIT_FIRST_0.
private static final int SHIFT_FIRST = OMIT_FIRST_BASE + OMIT_FIRST_LAST_LIMIT + 1;
private static final int SHIFT_ALL = SHIFT_FIRST + 1;
// Bundle of 0-terminated strings.
private static final String PREFIX_SUFFIX_SRC = "# #s #, #e #.# the #.com/#\u00C2\u00A0# of # and"
+ " # in # to #\"#\">#\n#]# for # a # that #. # with #'# from # by #. The # on # as # is #ing"
+ " #\n\t#:#ed #(# at #ly #=\"# of the #. This #,# not #er #al #='#ful #ive #less #est #ize #"
+ "ous #";
private static final String TRANSFORMS_SRC = " !! ! , *! &! \" ! ) * * - ! # ! #!*! "
+ "+ ,$ ! - % . / # 0 1 . \" 2 3!* 4% ! # / 5 6 7 8 0 1 & $ 9 + : "
+ " ; < ' != > ?! 4 @ 4 2 & A *# ( B C& ) % ) !*# *-% A +! *. D! %' & E *6 F "
+ " G% ! *A *% H! D I!+! J!+ K +- *4! A L!*4 M N +6 O!*% +.! K *G P +%( ! G *D +D "
+ " Q +# *K!*G!+D!+# +G +A +4!+% +K!+4!*D!+K!*K";
private static void unpackTransforms(byte[] prefixSuffix,
int[] prefixSuffixHeads, int[] transforms, String prefixSuffixSrc, String transformsSrc) {
final int n = prefixSuffixSrc.length();
int index = 1;
int j = 0;
for (int i = 0; i < n; ++i) {
final char c = prefixSuffixSrc.charAt(i);
if (c == 35) { // == #
prefixSuffixHeads[index++] = j;
} else {
prefixSuffix[j++] = (byte) c;
}
}
for (int i = 0; i < NUM_RFC_TRANSFORMS * 3; ++i) {
transforms[i] = transformsSrc.charAt(i) - 32;
}
}
static {
unpackTransforms(RFC_TRANSFORMS.prefixSuffixStorage, RFC_TRANSFORMS.prefixSuffixHeads,
RFC_TRANSFORMS.triplets, PREFIX_SUFFIX_SRC, TRANSFORMS_SRC);
}
static int transformDictionaryWord(byte[] dst, int dstOffset, ByteBuffer src, int srcOffset,
int len, Transforms transforms, int transformIndex) {
int offset = dstOffset;
final int[] triplets = transforms.triplets;
final byte[] prefixSuffixStorage = transforms.prefixSuffixStorage;
final int[] prefixSuffixHeads = transforms.prefixSuffixHeads;
final int transformOffset = 3 * transformIndex;
final int prefixIdx = triplets[transformOffset];
final int transformType = triplets[transformOffset + 1];
final int suffixIdx = triplets[transformOffset + 2];
int prefix = prefixSuffixHeads[prefixIdx];
final int prefixEnd = prefixSuffixHeads[prefixIdx + 1];
int suffix = prefixSuffixHeads[suffixIdx];
final int suffixEnd = prefixSuffixHeads[suffixIdx + 1];
int omitFirst = transformType - OMIT_FIRST_BASE;
int omitLast = transformType - OMIT_LAST_BASE;
if (omitFirst < 1 || omitFirst > OMIT_FIRST_LAST_LIMIT) {
omitFirst = 0;
}
if (omitLast < 1 || omitLast > OMIT_FIRST_LAST_LIMIT) {
omitLast = 0;
}
// Copy prefix.
while (prefix != prefixEnd) {
dst[offset++] = prefixSuffixStorage[prefix++];
}
// Copy trimmed word.
if (omitFirst > len) {
omitFirst = len;
}
srcOffset += omitFirst;
len -= omitFirst;
len -= omitLast;
int i = len;
while (i > 0) {
dst[offset++] = src.get(srcOffset++);
i--;
}
// Ferment.
if (transformType == UPPERCASE_FIRST || transformType == UPPERCASE_ALL) {
int uppercaseOffset = offset - len;
if (transformType == UPPERCASE_FIRST) {
len = 1;
}
while (len > 0) {
final int c0 = dst[uppercaseOffset] & 0xFF;
if (c0 < 0xC0) {
if (c0 >= 97 && c0 <= 122) { // in [a..z] range
dst[uppercaseOffset] ^= (byte) 32;
}
uppercaseOffset += 1;
len -= 1;
} else if (c0 < 0xE0) {
dst[uppercaseOffset + 1] ^= (byte) 32;
uppercaseOffset += 2;
len -= 2;
} else {
dst[uppercaseOffset + 2] ^= (byte) 5;
uppercaseOffset += 3;
len -= 3;
}
}
} else if (transformType == SHIFT_FIRST || transformType == SHIFT_ALL) {
int shiftOffset = offset - len;
final short param = transforms.params[transformIndex];
/* Limited sign extension: scalar < (1 << 24). */
int scalar = (param & 0x7FFF) + (0x1000000 - (param & 0x8000));
while (len > 0) {
int step = 1;
final int c0 = dst[shiftOffset] & 0xFF;
if (c0 < 0x80) {
/* 1-byte rune / 0sssssss / 7 bit scalar (ASCII). */
scalar += c0;
dst[shiftOffset] = (byte) (scalar & 0x7F);
} else if (c0 < 0xC0) {
/* Continuation / 10AAAAAA. */
} else if (c0 < 0xE0) {
/* 2-byte rune / 110sssss AAssssss / 11 bit scalar. */
if (len >= 2) {
final byte c1 = dst[shiftOffset + 1];
scalar += (c1 & 0x3F) | ((c0 & 0x1F) << 6);
dst[shiftOffset] = (byte) (0xC0 | ((scalar >> 6) & 0x1F));
dst[shiftOffset + 1] = (byte) ((c1 & 0xC0) | (scalar & 0x3F));
step = 2;
} else {
step = len;
}
} else if (c0 < 0xF0) {
/* 3-byte rune / 1110ssss AAssssss BBssssss / 16 bit scalar. */
if (len >= 3) {
final byte c1 = dst[shiftOffset + 1];
final byte c2 = dst[shiftOffset + 2];
scalar += (c2 & 0x3F) | ((c1 & 0x3F) << 6) | ((c0 & 0x0F) << 12);
dst[shiftOffset] = (byte) (0xE0 | ((scalar >> 12) & 0x0F));
dst[shiftOffset + 1] = (byte) ((c1 & 0xC0) | ((scalar >> 6) & 0x3F));
dst[shiftOffset + 2] = (byte) ((c2 & 0xC0) | (scalar & 0x3F));
step = 3;
} else {
step = len;
}
} else if (c0 < 0xF8) {
/* 4-byte rune / 11110sss AAssssss BBssssss CCssssss / 21 bit scalar. */
if (len >= 4) {
final byte c1 = dst[shiftOffset + 1];
final byte c2 = dst[shiftOffset + 2];
final byte c3 = dst[shiftOffset + 3];
scalar += (c3 & 0x3F) | ((c2 & 0x3F) << 6) | ((c1 & 0x3F) << 12) | ((c0 & 0x07) << 18);
dst[shiftOffset] = (byte) (0xF0 | ((scalar >> 18) & 0x07));
dst[shiftOffset + 1] = (byte) ((c1 & 0xC0) | ((scalar >> 12) & 0x3F));
dst[shiftOffset + 2] = (byte) ((c2 & 0xC0) | ((scalar >> 6) & 0x3F));
dst[shiftOffset + 3] = (byte) ((c3 & 0xC0) | (scalar & 0x3F));
step = 4;
} else {
step = len;
}
}
shiftOffset += step;
len -= step;
if (transformType == SHIFT_FIRST) {
len = 0;
}
}
}
// Copy suffix.
while (suffix != suffixEnd) {
dst[offset++] = prefixSuffixStorage[suffix++];
}
return offset - dstOffset;
}
}