write.c 4.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183
  1. #include <u.h>
  2. #include <libc.h>
  3. #include <draw.h>
  4. #include <memdraw.h>
  5. #define CHUNK 8000
  6. #define HSHIFT 3 /* HSHIFT==5 runs slightly faster, but hash table is 64x bigger */
  7. #define NHASH (1<<(HSHIFT*NMATCH))
  8. #define HMASK (NHASH-1)
  9. #define hupdate(h, c) ((((h)<<HSHIFT)^(c))&HMASK)
  10. typedef struct Hlist Hlist;
  11. struct Hlist{
  12. uchar *s;
  13. Hlist *next, *prev;
  14. };
  15. int
  16. writememimage(int fd, Memimage *i)
  17. {
  18. uchar *outbuf, *outp, *eout; /* encoded data, pointer, end */
  19. uchar *loutp; /* start of encoded line */
  20. Hlist *hash; /* heads of hash chains of past strings */
  21. Hlist *chain, *hp; /* hash chain members, pointer */
  22. Hlist *cp; /* next Hlist to fall out of window */
  23. int h; /* hash value */
  24. uchar *line, *eline; /* input line, end pointer */
  25. uchar *data, *edata; /* input buffer, end pointer */
  26. ulong n; /* length of input buffer */
  27. ulong nb; /* # of bytes returned by unloadimage */
  28. int bpl; /* input line length */
  29. int offs, runlen; /* offset, length of consumed data */
  30. uchar dumpbuf[NDUMP]; /* dump accumulator */
  31. int ndump; /* length of dump accumulator */
  32. int miny, dy; /* y values while unloading input */
  33. int ncblock; /* size of compressed blocks */
  34. Rectangle r;
  35. uchar *p, *q, *s, *es, *t;
  36. char hdr[11+5*12+1];
  37. char cbuf[20];
  38. r = i->r;
  39. bpl = bytesperline(r, i->depth);
  40. n = Dy(r)*bpl;
  41. data = malloc(n);
  42. ncblock = _compblocksize(r, i->depth);
  43. outbuf = malloc(ncblock);
  44. hash = malloc(NHASH*sizeof(Hlist));
  45. chain = malloc(NMEM*sizeof(Hlist));
  46. if(data == 0 || outbuf == 0 || hash == 0 || chain == 0){
  47. ErrOut:
  48. free(data);
  49. free(outbuf);
  50. free(hash);
  51. free(chain);
  52. return -1;
  53. }
  54. for(miny = r.min.y; miny != r.max.y; miny += dy){
  55. dy = r.max.y-miny;
  56. if(dy*bpl > CHUNK)
  57. dy = CHUNK/bpl;
  58. nb = unloadmemimage(i, Rect(r.min.x, miny, r.max.x, miny+dy),
  59. data+(miny-r.min.y)*bpl, dy*bpl);
  60. if(nb != dy*bpl)
  61. goto ErrOut;
  62. }
  63. sprint(hdr, "compressed\n%11s %11d %11d %11d %11d ",
  64. chantostr(cbuf, i->chan), r.min.x, r.min.y, r.max.x, r.max.y);
  65. if(write(fd, hdr, 11+5*12) != 11+5*12)
  66. goto ErrOut;
  67. edata = data+n;
  68. eout = outbuf+ncblock;
  69. line = data;
  70. r.max.y = r.min.y;
  71. while(line != edata){
  72. memset(hash, 0, NHASH*sizeof(Hlist));
  73. memset(chain, 0, NMEM*sizeof(Hlist));
  74. cp = chain;
  75. h = 0;
  76. outp = outbuf;
  77. for(n = 0; n != NMATCH; n++)
  78. h = hupdate(h, line[n]);
  79. loutp = outbuf;
  80. while(line != edata){
  81. ndump = 0;
  82. eline = line+bpl;
  83. for(p = line; p != eline; ){
  84. if(eline-p < NRUN)
  85. es = eline;
  86. else
  87. es = p+NRUN;
  88. q = 0;
  89. runlen = 0;
  90. for(hp = hash[h].next; hp; hp = hp->next){
  91. s = p + runlen;
  92. if(s >= es)
  93. continue;
  94. t = hp->s + runlen;
  95. for(; s >= p; s--)
  96. if(*s != *t--)
  97. goto matchloop;
  98. t += runlen+2;
  99. s += runlen+2;
  100. for(; s < es; s++)
  101. if(*s != *t++)
  102. break;
  103. n = s-p;
  104. if(n > runlen){
  105. runlen = n;
  106. q = hp->s;
  107. if(n == NRUN)
  108. break;
  109. }
  110. matchloop: ;
  111. }
  112. if(runlen < NMATCH){
  113. if(ndump == NDUMP){
  114. if(eout-outp < ndump+1)
  115. goto Bfull;
  116. *outp++ = ndump-1+128;
  117. memmove(outp, dumpbuf, ndump);
  118. outp += ndump;
  119. ndump = 0;
  120. }
  121. dumpbuf[ndump++] = *p;
  122. runlen = 1;
  123. }
  124. else{
  125. if(ndump != 0){
  126. if(eout-outp < ndump+1)
  127. goto Bfull;
  128. *outp++ = ndump-1+128;
  129. memmove(outp, dumpbuf, ndump);
  130. outp += ndump;
  131. ndump = 0;
  132. }
  133. offs = p-q-1;
  134. if(eout-outp < 2)
  135. goto Bfull;
  136. *outp++ = ((runlen-NMATCH)<<2) + (offs>>8);
  137. *outp++ = offs&255;
  138. }
  139. for(q = p+runlen; p != q; p++){
  140. if(cp->prev)
  141. cp->prev->next = 0;
  142. cp->next = hash[h].next;
  143. cp->prev = &hash[h];
  144. if(cp->next)
  145. cp->next->prev = cp;
  146. cp->prev->next = cp;
  147. cp->s = p;
  148. if(++cp == &chain[NMEM])
  149. cp = chain;
  150. if(edata-p > NMATCH)
  151. h = hupdate(h, p[NMATCH]);
  152. }
  153. }
  154. if(ndump != 0){
  155. if(eout-outp < ndump+1)
  156. goto Bfull;
  157. *outp++ = ndump-1+128;
  158. memmove(outp, dumpbuf, ndump);
  159. outp += ndump;
  160. }
  161. line = eline;
  162. loutp = outp;
  163. r.max.y++;
  164. }
  165. Bfull:
  166. if(loutp == outbuf)
  167. goto ErrOut;
  168. n = loutp-outbuf;
  169. sprint(hdr, "%11d %11ld ", r.max.y, n);
  170. write(fd, hdr, 2*12);
  171. write(fd, outbuf, n);
  172. r.min.y = r.max.y;
  173. }
  174. free(data);
  175. free(outbuf);
  176. free(hash);
  177. free(chain);
  178. return 0;
  179. }