1 /* 2 * Copyright 2011 Google Inc. All Rights Reserved. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.typography.font.tools.conversion.eot; 18 19 /** 20 * Adaptive huffman coder for LZCOMP compression algorithm 21 * 22 * @author Raph Levien 23 */ 24 public class HuffmanEncoder { 25 26 private static final int ROOT = 1; 27 28 private TreeNode[] tree; 29 private short[] symbolIndex; 30 private int bitCount2; 31 private int range; 32 private BitIOWriter bits; 33 34 private static class TreeNode { 35 short up; 36 short left; 37 short right; 38 short code; 39 int weight; 40 } 41 HuffmanEncoder(BitIOWriter bits, int range)42 public HuffmanEncoder(BitIOWriter bits, int range) { 43 this.bits = bits; 44 this.range = range; 45 bitsUsed(range - 1); 46 if (range > 256 && range < 512) { 47 bitCount2 = bitsUsed(range - 257); 48 } else { 49 bitCount2 = 0; 50 } 51 symbolIndex = new short[range]; 52 int limit = 2 * range; 53 tree = new TreeNode[limit]; 54 for (int i = 0; i < limit; i++) { 55 tree[i] = new TreeNode(); 56 } 57 for (int i = 2; i < limit; i++) { 58 tree[i].up = (short)(i / 2); 59 tree[i].weight = 1; 60 } 61 for (int i = 1; i < range; i++) { 62 tree[i].left = (short)(2 * i); 63 tree[i].right = (short)(2 * i + 1); 64 } 65 for (int i = 0; i < range; i++) { 66 tree[i].code = -1; 67 tree[range + i].code = (short)i; 68 tree[range + i].left = -1; 69 tree[range + i].right = -1; 70 symbolIndex[i] = (short)(range + i); 71 } 72 initWeight(ROOT); 73 if (bitCount2 != 0) { 74 updateWeight(symbolIndex[256]); 75 updateWeight(symbolIndex[257]); 76 // assert (258 < range) 77 for (int i = 0; i < 12; i++) { 78 updateWeight(symbolIndex[range - 3]); 79 } 80 for (int i = 0; i < 6; i++) { 81 updateWeight(symbolIndex[range - 2]); 82 } 83 } else { 84 for (int j = 0; j < 2; j++) { 85 for (int i = 0; i < range; i++) { 86 updateWeight(symbolIndex[i]); 87 } 88 } 89 } 90 } 91 92 /* Check tree for internal consistency, return problem string or null if ok */ checkTree()93 String checkTree() { 94 for (int i = ROOT; i < range; i++) { 95 if (tree[i].code < 0) { 96 if (tree[tree[i].left].up != i) { 97 return "tree[tree[" + i + "].left].up == " + tree[tree[i].left].up + ", expected " + i; 98 } 99 if (tree[tree[i].right].up != i) { 100 return "tree[tree[" + i + "].right].up == " + tree[tree[i].right].up + ", expected " + i; 101 } 102 } 103 } 104 for (int i = ROOT; i < range; i++) { 105 if (tree[i].code < 0) { 106 if (tree[i].weight != tree[tree[i].left].weight + tree[tree[i].right].weight) { 107 return "tree[" + i + "].weight == " + tree[i].weight + ", expected " + 108 tree[tree[i].left].weight + " + " + tree[tree[i].right].weight; 109 } 110 } 111 } 112 int j = range * 2 - 1; 113 for (int i = ROOT; i < j; i++) { 114 if (tree[i].weight < tree[i + 1].weight) { 115 return "tree[" + i + "].weight == " + tree[i].weight + 116 ", tree[" + (i + 1) + ".weight == " + tree[i+1].weight + ", not >="; 117 } 118 } 119 for (int i = ROOT + 1; i < j; i++) { 120 if (tree[i].code < 0) { 121 int a = tree[i].left; 122 int b = tree[i].right; 123 if (a - b != 1 && a - b != -1) { 124 return "tree[" + i + "].left == " + tree[i].left + 125 ", tree[" + i + "].right] == " +tree[i].right + ", siblings not adjacent"; 126 } 127 } 128 } 129 for (int i = ROOT + 1; i < range * 2; i++) { 130 int a = tree[i].up; 131 if (tree[a].left != i && tree[a].right != i) { 132 return "tree[" + a + "].left != " + i + " && tree[" + a + "].right != " + i; 133 } 134 } 135 136 return null; 137 } 138 initWeight(int a)139 private int initWeight(int a) { 140 if (tree[a].code < 0) { 141 tree[a].weight = initWeight(tree[a].left) + initWeight(tree[a].right); 142 } 143 return tree[a].weight; 144 } 145 updateWeight(int a)146 private void updateWeight(int a) { 147 for (; a != ROOT; a = tree[a].up) { 148 int weightA = tree[a].weight; 149 int b = a - 1; 150 if (tree[b].weight == weightA) { 151 do { 152 b--; 153 } while (tree[b].weight == weightA); 154 b++; 155 if (b > ROOT) { 156 swapNodes(a, b); 157 a = b; 158 } 159 } 160 weightA++; 161 tree[a].weight = weightA; 162 } 163 tree[a].weight++; 164 } 165 swapNodes(int a, int b)166 private void swapNodes(int a, int b) { 167 short upa = tree[a].up; 168 short upb = tree[b].up; 169 TreeNode tmp = tree[a]; 170 tree[a] = tree[b]; 171 tree[b] = tmp; 172 tree[a].up = upa; 173 tree[b].up = upb; 174 int code = tree[a].code; 175 if (code < 0) { 176 tree[tree[a].left].up = (short)a; 177 tree[tree[a].right].up = (short)a; 178 } else { 179 symbolIndex[code] = (short)a; 180 } 181 code = tree[b].code; 182 if (code < 0) { 183 tree[tree[b].left].up = (short)b; 184 tree[tree[b].right].up = (short)b; 185 } else { 186 symbolIndex[code] = (short)b; 187 } 188 } 189 writeSymbolCost(int symbol)190 public int writeSymbolCost(int symbol) { 191 int a = symbolIndex[symbol]; 192 int sp = 0; 193 do { 194 sp++; 195 a = tree[a].up; 196 } while (a != ROOT); 197 return sp << 16; 198 } 199 writeSymbol(int symbol)200 public void writeSymbol(int symbol) { 201 int a = symbolIndex[symbol]; 202 int aa = a; 203 boolean[] stack = new boolean[50]; 204 int sp = 0; 205 do { 206 int up = tree[a].up; 207 stack[sp++] = tree[up].right == a; 208 a = up; 209 } while (a != ROOT); 210 do { 211 bits.writeBit(stack[--sp]); 212 } while (sp > 0); 213 updateWeight(aa); 214 } 215 bitsUsed(int x)216 public static int bitsUsed(int x) { 217 int i; 218 for (i = 32; i > 1; i--) { 219 if ((x & (1 << (i - 1))) != 0) 220 break; 221 } 222 return i; 223 } 224 } 225