thwack.c 7.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381
  1. #include "u.h"
  2. #include "lib.h"
  3. #include "mem.h"
  4. #include "dat.h"
  5. #include "fns.h"
  6. #include "thwack.h"
  7. typedef struct Huff Huff;
  8. enum
  9. {
  10. MaxFastLen = 9,
  11. BigLenCode = 0x1f4, /* minimum code for large lenth encoding */
  12. BigLenBits = 9,
  13. BigLenBase = 4 /* starting items to encode for big lens */
  14. };
  15. enum
  16. {
  17. StatBytes,
  18. StatOutBytes,
  19. StatLits,
  20. StatMatches,
  21. StatOffBits,
  22. StatLenBits,
  23. StatDelay,
  24. StatHist,
  25. MaxStat
  26. };
  27. struct Huff
  28. {
  29. short bits; /* length of the code */
  30. ulong encode; /* the code */
  31. };
  32. static Huff lentab[MaxFastLen] =
  33. {
  34. {2, 0x2}, /* 10 */
  35. {3, 0x6}, /* 110 */
  36. {5, 0x1c}, /* 11100 */
  37. {5, 0x1d}, /* 11101 */
  38. {6, 0x3c}, /* 111100 */
  39. {7, 0x7a}, /* 1111010 */
  40. {7, 0x7b}, /* 1111011 */
  41. {8, 0xf8}, /* 11111000 */
  42. {8, 0xf9}, /* 11111001 */
  43. };
  44. void
  45. thwackinit(Thwack *tw)
  46. {
  47. int i;
  48. memset(tw, 0, sizeof *tw);
  49. for(i = 0; i < EWinBlocks; i++){
  50. tw->blocks[i].data = tw->data[i];
  51. tw->blocks[i].edata = tw->blocks[i].data;
  52. tw->blocks[i].hash = tw->hash[i];
  53. tw->blocks[i].acked = 0;
  54. }
  55. }
  56. /*
  57. * acknowledgement for block seq & nearby preds
  58. */
  59. void
  60. thwackack(Thwack *tw, ulong seq, ulong mask)
  61. {
  62. int slot, b;
  63. slot = tw->slot;
  64. for(;;){
  65. slot--;
  66. if(slot < 0)
  67. slot += EWinBlocks;
  68. if(slot == tw->slot)
  69. break;
  70. if(tw->blocks[slot].seq != seq)
  71. continue;
  72. tw->blocks[slot].acked = 1;
  73. if(mask == 0)
  74. break;
  75. do{
  76. b = mask & 1;
  77. seq--;
  78. mask >>= 1;
  79. }while(!b);
  80. }
  81. }
  82. /*
  83. * find a string in the dictionary
  84. */
  85. static int
  86. thwmatch(ThwBlock *b, ThwBlock *eblocks, uchar **ss, uchar *esrc, ulong h)
  87. {
  88. int then, toff, w, ok;
  89. uchar *s, *t;
  90. s = *ss;
  91. if(esrc < s + MinMatch)
  92. return 0;
  93. toff = 0;
  94. for(; b < eblocks; b++){
  95. then = b->hash[(h ^ b->seq) & HashMask];
  96. toff += b->maxoff;
  97. w = (ushort)(then - b->begin);
  98. if(w >= b->maxoff)
  99. continue;
  100. /*
  101. * don't need to check for the end because
  102. * 1) s too close check above
  103. * 2) entries too close not added to hash tables
  104. */
  105. t = w + b->data;
  106. if(s[0] != t[0] || s[1] != t[1] || s[2] != t[2])
  107. continue;
  108. ok = b->edata - t;
  109. if(esrc - s > ok)
  110. esrc = s + ok;
  111. t += 3;
  112. for(s += 3; s < esrc; s++){
  113. if(*s != *t)
  114. break;
  115. t++;
  116. }
  117. *ss = s;
  118. return toff - w;
  119. }
  120. return 0;
  121. }
  122. /*
  123. * knuth vol. 3 multiplicative hashing
  124. * each byte x chosen according to rules
  125. * 1/4 < x < 3/10, 1/3 x < < 3/7, 4/7 < x < 2/3, 7/10 < x < 3/4
  126. * with reasonable spread between the bytes & their complements
  127. *
  128. * the 3 byte value appears to be as almost good as the 4 byte value,
  129. * and might be faster on some machines
  130. */
  131. /*
  132. #define hashit(c) (((ulong)(c) * 0x6b43a9) >> (24 - HashLog))
  133. */
  134. #define hashit(c) ((((ulong)(c) & 0xffffff) * 0x6b43a9b5) >> (32 - HashLog))
  135. /*
  136. * lz77 compression with single lookup in a hash table for each block
  137. */
  138. int
  139. thwack(Thwack *tw, uchar *dst, uchar *src, int n, ulong seq, ulong stats[ThwStats])
  140. {
  141. ThwBlock *eblocks, *b, blocks[CompBlocks];
  142. uchar *s, *ss, *sss, *esrc, *half, *twdst, *twdmax;
  143. ulong cont, cseq, bseq, cmask, code, twbits;
  144. int now, toff, lithist, h, len, slot, bits, use, twnbits, lits, matches, offbits, lenbits, nhist;
  145. if(n > ThwMaxBlock || n < MinMatch)
  146. return -1;
  147. twdst = dst;
  148. twdmax = dst + n;
  149. /*
  150. * add source to the coding window
  151. * there is always enough space
  152. */
  153. slot = tw->slot;
  154. b = &tw->blocks[slot];
  155. b->seq = seq;
  156. b->acked = 0;
  157. now = b->begin + b->maxoff;
  158. s = b->data;
  159. memmove(s, src, n);
  160. b->edata = s + n;
  161. b->begin = now;
  162. b->maxoff = n;
  163. /*
  164. * set up the history blocks
  165. */
  166. cseq = seq;
  167. cmask = 0;
  168. *blocks = *b;
  169. b = blocks;
  170. b->maxoff = 0;
  171. b++;
  172. nhist = 0;
  173. while(b < blocks + CompBlocks){
  174. slot--;
  175. if(slot < 0)
  176. slot += EWinBlocks;
  177. if(slot == tw->slot)
  178. break;
  179. if(!tw->blocks[slot].acked)
  180. continue;
  181. bseq = tw->blocks[slot].seq;
  182. if(cseq == seq){
  183. if(seq - bseq >= MaxSeqStart)
  184. break;
  185. cseq = bseq;
  186. }else if(cseq - bseq > MaxSeqMask)
  187. break;
  188. else
  189. cmask |= 1 << (cseq - bseq - 1);
  190. *b = tw->blocks[slot];
  191. nhist += b->maxoff;
  192. b++;
  193. }
  194. eblocks = b;
  195. *twdst++ = seq - cseq;
  196. *twdst++ = cmask;
  197. cont = (s[0] << 16) | (s[1] << 8) | s[2];
  198. esrc = s + n;
  199. half = s + (n >> 1);
  200. twnbits = 0;
  201. twbits = 0;
  202. lits = 0;
  203. matches = 0;
  204. offbits = 0;
  205. lenbits = 0;
  206. lithist = ~0;
  207. while(s < esrc){
  208. h = hashit(cont);
  209. sss = s;
  210. toff = thwmatch(blocks, eblocks, &sss, esrc, h);
  211. ss = sss;
  212. len = ss - s;
  213. for(; twnbits >= 8; twnbits -= 8){
  214. if(twdst >= twdmax)
  215. return -1;
  216. *twdst++ = twbits >> (twnbits - 8);
  217. }
  218. if(len < MinMatch){
  219. toff = *s;
  220. lithist = (lithist << 1) | (toff < 32) | (toff > 127);
  221. if(lithist & 0x1e){
  222. twbits = (twbits << 9) | toff;
  223. twnbits += 9;
  224. }else if(lithist & 1){
  225. toff = (toff + 64) & 0xff;
  226. if(toff < 96){
  227. twbits = (twbits << 10) | toff;
  228. twnbits += 10;
  229. }else{
  230. twbits = (twbits << 11) | toff;
  231. twnbits += 11;
  232. }
  233. }else{
  234. twbits = (twbits << 8) | toff;
  235. twnbits += 8;
  236. }
  237. lits++;
  238. blocks->maxoff++;
  239. /*
  240. * speed hack
  241. * check for compression progress, bail if none achieved
  242. */
  243. if(s > half){
  244. if(4 * blocks->maxoff < 5 * lits)
  245. return -1;
  246. half = esrc;
  247. }
  248. if(s + MinMatch <= esrc){
  249. blocks->hash[(h ^ blocks->seq) & HashMask] = now;
  250. if(s + MinMatch < esrc)
  251. cont = (cont << 8) | s[MinMatch];
  252. }
  253. now++;
  254. s++;
  255. continue;
  256. }
  257. blocks->maxoff += len;
  258. matches++;
  259. /*
  260. * length of match
  261. */
  262. len -= MinMatch;
  263. if(len < MaxFastLen){
  264. bits = lentab[len].bits;
  265. twbits = (twbits << bits) | lentab[len].encode;
  266. twnbits += bits;
  267. lenbits += bits;
  268. }else{
  269. code = BigLenCode;
  270. bits = BigLenBits;
  271. use = BigLenBase;
  272. len -= MaxFastLen;
  273. while(len >= use){
  274. len -= use;
  275. code = (code + use) << 1;
  276. use <<= (bits & 1) ^ 1;
  277. bits++;
  278. }
  279. twbits = (twbits << bits) | (code + len);
  280. twnbits += bits;
  281. lenbits += bits;
  282. for(; twnbits >= 8; twnbits -= 8){
  283. if(twdst >= twdmax)
  284. return -1;
  285. *twdst++ = twbits >> (twnbits - 8);
  286. }
  287. }
  288. /*
  289. * offset in history
  290. */
  291. toff--;
  292. for(bits = OffBase; toff >= (1 << bits); bits++)
  293. ;
  294. if(bits < MaxOff+OffBase-1){
  295. twbits = (twbits << 3) | (bits - OffBase);
  296. if(bits != OffBase)
  297. bits--;
  298. twnbits += bits + 3;
  299. offbits += bits + 3;
  300. }else{
  301. twbits = (twbits << 4) | 0xe | (bits - (MaxOff+OffBase-1));
  302. bits--;
  303. twnbits += bits + 4;
  304. offbits += bits + 4;
  305. }
  306. twbits = (twbits << bits) | toff & ((1 << bits) - 1);
  307. for(; s != ss; s++){
  308. if(s + MinMatch <= esrc){
  309. h = hashit(cont);
  310. blocks->hash[(h ^ blocks->seq) & HashMask] = now;
  311. if(s + MinMatch < esrc)
  312. cont = (cont << 8) | s[MinMatch];
  313. }
  314. now++;
  315. }
  316. }
  317. if(twnbits & 7){
  318. twbits <<= 8 - (twnbits & 7);
  319. twnbits += 8 - (twnbits & 7);
  320. }
  321. for(; twnbits >= 8; twnbits -= 8){
  322. if(twdst >= twdmax)
  323. return -1;
  324. *twdst++ = twbits >> (twnbits - 8);
  325. }
  326. tw->slot++;
  327. if(tw->slot >= EWinBlocks)
  328. tw->slot = 0;
  329. stats[StatBytes] += blocks->maxoff;
  330. stats[StatLits] += lits;
  331. stats[StatMatches] += matches;
  332. stats[StatOffBits] += offbits;
  333. stats[StatLenBits] += lenbits;
  334. stats[StatDelay] = stats[StatDelay]*7/8 + dst[0];
  335. stats[StatHist] = stats[StatHist]*7/8 + nhist;
  336. stats[StatOutBytes] += twdst - dst;
  337. return twdst - dst;
  338. }