writeimage.c 4.4 KB

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