1 8a3b2ceb 2004-04-24 devnull #include <u.h>
2 8a3b2ceb 2004-04-24 devnull #include <libc.h>
3 8a3b2ceb 2004-04-24 devnull #include <bio.h>
4 8a3b2ceb 2004-04-24 devnull #include "sky.h"
6 8a3b2ceb 2004-04-24 devnull static void qtree_expand(Biobuf*, uchar*, int, int, uchar*);
7 8a3b2ceb 2004-04-24 devnull static void qtree_copy(uchar*, int, int, uchar*, int);
8 8a3b2ceb 2004-04-24 devnull static void qtree_bitins(uchar*, int, int, Pix*, int, int);
9 8a3b2ceb 2004-04-24 devnull static void read_bdirect(Biobuf*, Pix*, int, int, int, uchar*, int);
12 8a3b2ceb 2004-04-24 devnull qtree_decode(Biobuf *infile, Pix *a, int n, int nqx, int nqy, int nbitplanes)
14 8a3b2ceb 2004-04-24 devnull int log2n, k, bit, b, nqmax;
15 8a3b2ceb 2004-04-24 devnull int nx,ny,nfx,nfy,c;
16 8a3b2ceb 2004-04-24 devnull int nqx2, nqy2;
17 8a3b2ceb 2004-04-24 devnull unsigned char *scratch;
20 8a3b2ceb 2004-04-24 devnull * log2n is log2 of max(nqx,nqy) rounded up to next power of 2
22 8a3b2ceb 2004-04-24 devnull nqmax = nqy;
23 8a3b2ceb 2004-04-24 devnull if(nqx > nqmax)
24 8a3b2ceb 2004-04-24 devnull nqmax = nqx;
25 8a3b2ceb 2004-04-24 devnull log2n = log(nqmax)/LN2+0.5;
26 8a3b2ceb 2004-04-24 devnull if (nqmax > (1<<log2n))
30 8a3b2ceb 2004-04-24 devnull * allocate scratch array for working space
32 8a3b2ceb 2004-04-24 devnull nqx2 = (nqx+1)/2;
33 8a3b2ceb 2004-04-24 devnull nqy2 = (nqy+1)/2;
34 8a3b2ceb 2004-04-24 devnull scratch = (uchar*)malloc(nqx2*nqy2);
35 8a3b2ceb 2004-04-24 devnull if(scratch == nil) {
36 8a3b2ceb 2004-04-24 devnull fprint(2, "qtree_decode: insufficient memory\n");
37 8a3b2ceb 2004-04-24 devnull exits("memory");
41 8a3b2ceb 2004-04-24 devnull * now decode each bit plane, starting at the top
42 8a3b2ceb 2004-04-24 devnull * A is assumed to be initialized to zero
44 8a3b2ceb 2004-04-24 devnull for(bit = nbitplanes-1; bit >= 0; bit--) {
46 8a3b2ceb 2004-04-24 devnull * Was bitplane was quadtree-coded or written directly?
48 8a3b2ceb 2004-04-24 devnull b = input_nybble(infile);
49 8a3b2ceb 2004-04-24 devnull if(b == 0) {
51 8a3b2ceb 2004-04-24 devnull * bit map was written directly
53 8a3b2ceb 2004-04-24 devnull read_bdirect(infile, a, n, nqx, nqy, scratch, bit);
55 8a3b2ceb 2004-04-24 devnull if(b != 0xf) {
56 8a3b2ceb 2004-04-24 devnull fprint(2, "qtree_decode: bad format code %x\n",b);
57 8a3b2ceb 2004-04-24 devnull exits("format");
60 8a3b2ceb 2004-04-24 devnull * bitmap was quadtree-coded, do log2n expansions
61 8a3b2ceb 2004-04-24 devnull * read first code
64 8a3b2ceb 2004-04-24 devnull scratch[0] = input_huffman(infile);
67 8a3b2ceb 2004-04-24 devnull * do log2n expansions, reading codes from file as necessary
71 8a3b2ceb 2004-04-24 devnull nfx = nqx;
72 8a3b2ceb 2004-04-24 devnull nfy = nqy;
73 8a3b2ceb 2004-04-24 devnull c = 1<<log2n;
74 8a3b2ceb 2004-04-24 devnull for(k = 1; k<log2n; k++) {
76 8a3b2ceb 2004-04-24 devnull * this somewhat cryptic code generates the sequence
77 8a3b2ceb 2004-04-24 devnull * n[k-1] = (n[k]+1)/2 where n[log2n]=nqx or nqy
79 8a3b2ceb 2004-04-24 devnull c = c>>1;
80 8a3b2ceb 2004-04-24 devnull nx = nx<<1;
81 8a3b2ceb 2004-04-24 devnull ny = ny<<1;
82 8a3b2ceb 2004-04-24 devnull if(nfx <= c)
85 8a3b2ceb 2004-04-24 devnull nfx -= c;
86 8a3b2ceb 2004-04-24 devnull if(nfy <= c)
89 8a3b2ceb 2004-04-24 devnull nfy -= c;
90 8a3b2ceb 2004-04-24 devnull qtree_expand(infile, scratch, nx, ny, scratch);
94 8a3b2ceb 2004-04-24 devnull * copy last set of 4-bit codes to bitplane bit of array a
96 8a3b2ceb 2004-04-24 devnull qtree_bitins(scratch, nqx, nqy, a, n, bit);
99 8a3b2ceb 2004-04-24 devnull free(scratch);
103 8a3b2ceb 2004-04-24 devnull * do one quadtree expansion step on array a[(nqx+1)/2,(nqy+1)/2]
104 8a3b2ceb 2004-04-24 devnull * results put into b[nqx,nqy] (which may be the same as a)
108 8a3b2ceb 2004-04-24 devnull qtree_expand(Biobuf *infile, uchar *a, int nx, int ny, uchar *b)
110 8a3b2ceb 2004-04-24 devnull uchar *b1;
113 8a3b2ceb 2004-04-24 devnull * first copy a to b, expanding each 4-bit value
115 8a3b2ceb 2004-04-24 devnull qtree_copy(a, nx, ny, b, ny);
118 8a3b2ceb 2004-04-24 devnull * now read new 4-bit values into b for each non-zero element
120 8a3b2ceb 2004-04-24 devnull b1 = &b[nx*ny];
121 8a3b2ceb 2004-04-24 devnull while(b1 > b) {
123 8a3b2ceb 2004-04-24 devnull if(*b1 != 0)
124 8a3b2ceb 2004-04-24 devnull *b1 = input_huffman(infile);
129 8a3b2ceb 2004-04-24 devnull * copy 4-bit values from a[(nx+1)/2,(ny+1)/2] to b[nx,ny], expanding
130 8a3b2ceb 2004-04-24 devnull * each value to 2x2 pixels
131 8a3b2ceb 2004-04-24 devnull * a,b may be same array
135 8a3b2ceb 2004-04-24 devnull qtree_copy(uchar *a, int nx, int ny, uchar *b, int n)
137 8a3b2ceb 2004-04-24 devnull int i, j, k, nx2, ny2;
138 8a3b2ceb 2004-04-24 devnull int s00, s10;
141 8a3b2ceb 2004-04-24 devnull * first copy 4-bit values to b
142 8a3b2ceb 2004-04-24 devnull * start at end in case a,b are same array
144 8a3b2ceb 2004-04-24 devnull nx2 = (nx+1)/2;
145 8a3b2ceb 2004-04-24 devnull ny2 = (ny+1)/2;
146 8a3b2ceb 2004-04-24 devnull k = ny2*(nx2-1) + ny2-1; /* k is index of a[i,j] */
147 8a3b2ceb 2004-04-24 devnull for (i = nx2-1; i >= 0; i--) {
148 8a3b2ceb 2004-04-24 devnull s00 = 2*(n*i+ny2-1); /* s00 is index of b[2*i,2*j] */
149 8a3b2ceb 2004-04-24 devnull for (j = ny2-1; j >= 0; j--) {
150 8a3b2ceb 2004-04-24 devnull b[s00] = a[k];
152 8a3b2ceb 2004-04-24 devnull s00 -= 2;
157 8a3b2ceb 2004-04-24 devnull * now expand each 2x2 block
159 8a3b2ceb 2004-04-24 devnull for(i = 0; i<nx-1; i += 2) {
160 8a3b2ceb 2004-04-24 devnull s00 = n*i; /* s00 is index of b[i,j] */
161 8a3b2ceb 2004-04-24 devnull s10 = s00+n; /* s10 is index of b[i+1,j] */
162 8a3b2ceb 2004-04-24 devnull for(j = 0; j<ny-1; j += 2) {
163 8a3b2ceb 2004-04-24 devnull b[s10+1] = b[s00] & 1;
164 8a3b2ceb 2004-04-24 devnull b[s10 ] = (b[s00]>>1) & 1;
165 8a3b2ceb 2004-04-24 devnull b[s00+1] = (b[s00]>>2) & 1;
166 8a3b2ceb 2004-04-24 devnull b[s00 ] = (b[s00]>>3) & 1;
167 8a3b2ceb 2004-04-24 devnull s00 += 2;
168 8a3b2ceb 2004-04-24 devnull s10 += 2;
170 8a3b2ceb 2004-04-24 devnull if(j < ny) {
172 8a3b2ceb 2004-04-24 devnull * row size is odd, do last element in row
173 8a3b2ceb 2004-04-24 devnull * s00+1, s10+1 are off edge
175 8a3b2ceb 2004-04-24 devnull b[s10 ] = (b[s00]>>1) & 1;
176 8a3b2ceb 2004-04-24 devnull b[s00 ] = (b[s00]>>3) & 1;
179 8a3b2ceb 2004-04-24 devnull if(i < nx) {
181 8a3b2ceb 2004-04-24 devnull * column size is odd, do last row
182 8a3b2ceb 2004-04-24 devnull * s10, s10+1 are off edge
184 8a3b2ceb 2004-04-24 devnull s00 = n*i;
185 8a3b2ceb 2004-04-24 devnull for (j = 0; j<ny-1; j += 2) {
186 8a3b2ceb 2004-04-24 devnull b[s00+1] = (b[s00]>>2) & 1;
187 8a3b2ceb 2004-04-24 devnull b[s00 ] = (b[s00]>>3) & 1;
188 8a3b2ceb 2004-04-24 devnull s00 += 2;
190 8a3b2ceb 2004-04-24 devnull if(j < ny) {
192 8a3b2ceb 2004-04-24 devnull * both row and column size are odd, do corner element
193 8a3b2ceb 2004-04-24 devnull * s00+1, s10, s10+1 are off edge
195 8a3b2ceb 2004-04-24 devnull b[s00 ] = (b[s00]>>3) & 1;
201 8a3b2ceb 2004-04-24 devnull * Copy 4-bit values from a[(nx+1)/2,(ny+1)/2] to b[nx,ny], expanding
202 8a3b2ceb 2004-04-24 devnull * each value to 2x2 pixels and inserting into bitplane BIT of B.
203 8a3b2ceb 2004-04-24 devnull * A,B may NOT be same array (it wouldn't make sense to be inserting
204 8a3b2ceb 2004-04-24 devnull * bits into the same array anyway.)
208 8a3b2ceb 2004-04-24 devnull qtree_bitins(uchar *a, int nx, int ny, Pix *b, int n, int bit)
210 8a3b2ceb 2004-04-24 devnull int i, j;
211 8a3b2ceb 2004-04-24 devnull Pix *s00, *s10;
215 8a3b2ceb 2004-04-24 devnull * expand each 2x2 block
217 8a3b2ceb 2004-04-24 devnull for(i=0; i<nx-1; i+=2) {
218 8a3b2ceb 2004-04-24 devnull s00 = &b[n*i]; /* s00 is index of b[i,j] */
219 8a3b2ceb 2004-04-24 devnull s10 = s00+n; /* s10 is index of b[i+1,j] */
220 8a3b2ceb 2004-04-24 devnull for(j=0; j<ny-1; j+=2) {
221 8a3b2ceb 2004-04-24 devnull px = *a++;
222 8a3b2ceb 2004-04-24 devnull s10[1] |= ( px & 1) << bit;
223 8a3b2ceb 2004-04-24 devnull s10[0] |= ((px>>1) & 1) << bit;
224 8a3b2ceb 2004-04-24 devnull s00[1] |= ((px>>2) & 1) << bit;
225 8a3b2ceb 2004-04-24 devnull s00[0] |= ((px>>3) & 1) << bit;
226 8a3b2ceb 2004-04-24 devnull s00 += 2;
227 8a3b2ceb 2004-04-24 devnull s10 += 2;
229 8a3b2ceb 2004-04-24 devnull if(j < ny) {
231 8a3b2ceb 2004-04-24 devnull * row size is odd, do last element in row
232 8a3b2ceb 2004-04-24 devnull * s00+1, s10+1 are off edge
234 8a3b2ceb 2004-04-24 devnull px = *a++;
235 8a3b2ceb 2004-04-24 devnull s10[0] |= ((px>>1) & 1) << bit;
236 8a3b2ceb 2004-04-24 devnull s00[0] |= ((px>>3) & 1) << bit;
239 8a3b2ceb 2004-04-24 devnull if(i < nx) {
241 8a3b2ceb 2004-04-24 devnull * column size is odd, do last row
242 8a3b2ceb 2004-04-24 devnull * s10, s10+1 are off edge
244 8a3b2ceb 2004-04-24 devnull s00 = &b[n*i];
245 8a3b2ceb 2004-04-24 devnull for(j=0; j<ny-1; j+=2) {
246 8a3b2ceb 2004-04-24 devnull px = *a++;
247 8a3b2ceb 2004-04-24 devnull s00[1] |= ((px>>2) & 1) << bit;
248 8a3b2ceb 2004-04-24 devnull s00[0] |= ((px>>3) & 1) << bit;
249 8a3b2ceb 2004-04-24 devnull s00 += 2;
251 8a3b2ceb 2004-04-24 devnull if(j < ny) {
253 8a3b2ceb 2004-04-24 devnull * both row and column size are odd, do corner element
254 8a3b2ceb 2004-04-24 devnull * s00+1, s10, s10+1 are off edge
256 8a3b2ceb 2004-04-24 devnull s00[0] |= ((*a>>3) & 1) << bit;
263 8a3b2ceb 2004-04-24 devnull read_bdirect(Biobuf *infile, Pix *a, int n, int nqx, int nqy, uchar *scratch, int bit)
268 8a3b2ceb 2004-04-24 devnull * read bit image packed 4 pixels/nybble
270 8a3b2ceb 2004-04-24 devnull for(i = 0; i < ((nqx+1)/2) * ((nqy+1)/2); i++) {
271 8a3b2ceb 2004-04-24 devnull scratch[i] = input_nybble(infile);
275 8a3b2ceb 2004-04-24 devnull * insert in bitplane BIT of image A
277 8a3b2ceb 2004-04-24 devnull qtree_bitins(scratch, nqx, nqy, a, n, bit);
