unthwack.c 5.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297
  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. enum
  8. {
  9. DMaxFastLen = 7,
  10. DBigLenCode = 0x3c, /* minimum code for large lenth encoding */
  11. DBigLenBits = 6,
  12. DBigLenBase = 1 /* starting items to encode for big lens */
  13. };
  14. static uchar lenval[1 << (DBigLenBits - 1)] =
  15. {
  16. 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
  17. 3, 3, 3, 3, 3, 3, 3, 3,
  18. 4, 4, 4, 4,
  19. 5,
  20. 6,
  21. 255,
  22. 255
  23. };
  24. static uchar lenbits[] =
  25. {
  26. 0, 0, 0,
  27. 2, 3, 5, 5,
  28. };
  29. static uchar offbits[16] =
  30. {
  31. 5, 5, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 12, 13
  32. };
  33. static ushort offbase[16] =
  34. {
  35. 0, 0x20,
  36. 0x40, 0x60,
  37. 0x80, 0xc0,
  38. 0x100, 0x180,
  39. 0x200, 0x300,
  40. 0x400, 0x600,
  41. 0x800, 0xc00,
  42. 0x1000,
  43. 0x2000
  44. };
  45. void
  46. unthwackinit(Unthwack *ut)
  47. {
  48. int i;
  49. memset(ut, 0, sizeof *ut);
  50. for(i = 0; i < DWinBlocks; i++)
  51. ut->blocks[i].data = ut->data[i];
  52. }
  53. ulong
  54. unthwackstate(Unthwack *ut, uchar *mask)
  55. {
  56. ulong bseq, seq;
  57. int slot, m;
  58. seq = ~0UL;
  59. m = 0;
  60. slot = ut->slot;
  61. for(;;){
  62. slot--;
  63. if(slot < 0)
  64. slot += DWinBlocks;
  65. if(slot == ut->slot)
  66. break;
  67. if(ut->blocks[slot].maxoff == 0)
  68. continue;
  69. bseq = ut->blocks[slot].seq;
  70. if(seq == ~0UL)
  71. seq = bseq;
  72. else if(seq - bseq > MaxSeqMask)
  73. break;
  74. else
  75. m |= 1 << (seq - bseq - 1);
  76. }
  77. *mask = m;
  78. return seq;
  79. }
  80. /*
  81. * insert this block in it's correct sequence number order.
  82. * replace the oldest block, which is always pointed to by ut->slot.
  83. * the encoder doesn't use a history at wraparound,
  84. * so don't worry about that case.
  85. */
  86. static int
  87. unthwackinsert(Unthwack *ut, int len, ulong seq)
  88. {
  89. uchar *d;
  90. int slot, tslot;
  91. tslot = ut->slot;
  92. for(;;){
  93. slot = tslot - 1;
  94. if(slot < 0)
  95. slot += DWinBlocks;
  96. if(ut->blocks[slot].seq <= seq || ut->blocks[slot].maxoff == 0)
  97. break;
  98. d = ut->blocks[tslot].data;
  99. ut->blocks[tslot] = ut->blocks[slot];
  100. ut->blocks[slot].data = d;
  101. tslot = slot;
  102. }
  103. ut->blocks[tslot].seq = seq;
  104. ut->blocks[tslot].maxoff = len;
  105. ut->slot++;
  106. if(ut->slot >= DWinBlocks)
  107. ut->slot = 0;
  108. ut->blocks[ut->slot].seq = ~0UL;
  109. ut->blocks[ut->slot].maxoff = 0;
  110. return tslot;
  111. }
  112. int
  113. unthwack(Unthwack *ut, uchar *dst, int ndst, uchar *src, int nsrc, ulong seq)
  114. {
  115. UnthwBlock blocks[CompBlocks], *b, *eblocks;
  116. uchar *s, *d, *dmax, *smax, lit;
  117. ulong cmask, cseq, bseq, utbits;
  118. int i, off, len, bits, slot, use, code, utnbits, overbits, lithist;
  119. if(nsrc < 4 || nsrc > ThwMaxBlock)
  120. return -1;
  121. slot = ut->slot;
  122. b = blocks;
  123. *b = ut->blocks[slot];
  124. d = b->data;
  125. dmax = d + ndst;
  126. /*
  127. * set up the history blocks
  128. */
  129. cseq = seq - src[0];
  130. cmask = src[1];
  131. b++;
  132. while(cseq != seq && b < blocks + CompBlocks){
  133. slot--;
  134. if(slot < 0)
  135. slot += DWinBlocks;
  136. if(slot == ut->slot)
  137. break;
  138. bseq = ut->blocks[slot].seq;
  139. if(bseq == cseq){
  140. *b = ut->blocks[slot];
  141. b++;
  142. if(cmask == 0){
  143. cseq = seq;
  144. break;
  145. }
  146. do{
  147. bits = cmask & 1;
  148. cseq--;
  149. cmask >>= 1;
  150. }while(!bits);
  151. }
  152. }
  153. eblocks = b;
  154. if(cseq != seq){
  155. print("blocks dropped: seq=%ld cseq=%ld %d cmask=%#lx %#x\n", seq, cseq, src[0], cmask, src[1]);
  156. return -2;
  157. }
  158. smax = src + nsrc;
  159. src += 2;
  160. utnbits = 0;
  161. utbits = 0;
  162. overbits = 0;
  163. lithist = ~0;
  164. while(src < smax || utnbits - overbits >= MinDecode){
  165. while(utnbits <= 24){
  166. utbits <<= 8;
  167. if(src < smax)
  168. utbits |= *src++;
  169. else
  170. overbits += 8;
  171. utnbits += 8;
  172. }
  173. /*
  174. * literal
  175. */
  176. len = lenval[(utbits >> (utnbits - 5)) & 0x1f];
  177. if(len == 0){
  178. if(lithist & 0xf){
  179. utnbits -= 9;
  180. lit = (utbits >> utnbits) & 0xff;
  181. lit &= 255;
  182. }else{
  183. utnbits -= 8;
  184. lit = (utbits >> utnbits) & 0x7f;
  185. if(lit < 32){
  186. if(lit < 24){
  187. utnbits -= 2;
  188. lit = (lit << 2) | ((utbits >> utnbits) & 3);
  189. }else{
  190. utnbits -= 3;
  191. lit = (lit << 3) | ((utbits >> utnbits) & 7);
  192. }
  193. lit = (lit - 64) & 0xff;
  194. }
  195. }
  196. if(d >= dmax)
  197. return -1;
  198. *d++ = lit;
  199. lithist = (lithist << 1) | (lit < 32) | (lit > 127);
  200. blocks->maxoff++;
  201. continue;
  202. }
  203. /*
  204. * length
  205. */
  206. if(len < 255)
  207. utnbits -= lenbits[len];
  208. else{
  209. utnbits -= DBigLenBits;
  210. code = ((utbits >> utnbits) & ((1 << DBigLenBits) - 1)) - DBigLenCode;
  211. len = DMaxFastLen;
  212. use = DBigLenBase;
  213. bits = (DBigLenBits & 1) ^ 1;
  214. while(code >= use){
  215. len += use;
  216. code -= use;
  217. code <<= 1;
  218. utnbits--;
  219. if(utnbits < 0)
  220. return -1;
  221. code |= (utbits >> utnbits) & 1;
  222. use <<= bits;
  223. bits ^= 1;
  224. }
  225. len += code;
  226. while(utnbits <= 24){
  227. utbits <<= 8;
  228. if(src < smax)
  229. utbits |= *src++;
  230. else
  231. overbits += 8;
  232. utnbits += 8;
  233. }
  234. }
  235. /*
  236. * offset
  237. */
  238. utnbits -= 4;
  239. bits = (utbits >> utnbits) & 0xf;
  240. off = offbase[bits];
  241. bits = offbits[bits];
  242. utnbits -= bits;
  243. off |= (utbits >> utnbits) & ((1 << bits) - 1);
  244. off++;
  245. b = blocks;
  246. while(off > b->maxoff){
  247. off -= b->maxoff;
  248. b++;
  249. if(b >= eblocks)
  250. return -1;
  251. }
  252. if(d + len > dmax
  253. || b != blocks && len > off)
  254. return -1;
  255. s = b->data + b->maxoff - off;
  256. blocks->maxoff += len;
  257. for(i = 0; i < len; i++)
  258. d[i] = s[i];
  259. d += len;
  260. }
  261. if(utnbits < overbits)
  262. return -1;
  263. len = d - blocks->data;
  264. memmove(dst, blocks->data, len);
  265. unthwackinsert(ut, len, seq);
  266. return len;
  267. }