1 #include <u.h>
2 #include <libc.h>
3 #include <bio.h>
4 #include "sky.h"
5
6 static void qtree_expand(Biobuf*, uchar*, int, int, uchar*);
7 static void qtree_copy(uchar*, int, int, uchar*, int);
8 static void qtree_bitins(uchar*, int, int, Pix*, int, int);
9 static void read_bdirect(Biobuf*, Pix*, int, int, int, uchar*, int);
10
11 void
qtree_decode(Biobuf * infile,Pix * a,int n,int nqx,int nqy,int nbitplanes)12 qtree_decode(Biobuf *infile, Pix *a, int n, int nqx, int nqy, int nbitplanes)
13 {
14 int log2n, k, bit, b, nqmax;
15 int nx,ny,nfx,nfy,c;
16 int nqx2, nqy2;
17 unsigned char *scratch;
18
19 /*
20 * log2n is log2 of max(nqx,nqy) rounded up to next power of 2
21 */
22 nqmax = nqy;
23 if(nqx > nqmax)
24 nqmax = nqx;
25 log2n = log(nqmax)/LN2+0.5;
26 if (nqmax > (1<<log2n))
27 log2n++;
28
29 /*
30 * allocate scratch array for working space
31 */
32 nqx2 = (nqx+1)/2;
33 nqy2 = (nqy+1)/2;
34 scratch = (uchar*)malloc(nqx2*nqy2);
35 if(scratch == nil) {
36 fprint(2, "qtree_decode: insufficient memory\n");
37 exits("memory");
38 }
39
40 /*
41 * now decode each bit plane, starting at the top
42 * A is assumed to be initialized to zero
43 */
44 for(bit = nbitplanes-1; bit >= 0; bit--) {
45 /*
46 * Was bitplane was quadtree-coded or written directly?
47 */
48 b = input_nybble(infile);
49 if(b == 0) {
50 /*
51 * bit map was written directly
52 */
53 read_bdirect(infile, a, n, nqx, nqy, scratch, bit);
54 } else
55 if(b != 0xf) {
56 fprint(2, "qtree_decode: bad format code %x\n",b);
57 exits("format");
58 } else {
59 /*
60 * bitmap was quadtree-coded, do log2n expansions
61 * read first code
62 */
63
64 scratch[0] = input_huffman(infile);
65
66 /*
67 * do log2n expansions, reading codes from file as necessary
68 */
69 nx = 1;
70 ny = 1;
71 nfx = nqx;
72 nfy = nqy;
73 c = 1<<log2n;
74 for(k = 1; k<log2n; k++) {
75 /*
76 * this somewhat cryptic code generates the sequence
77 * n[k-1] = (n[k]+1)/2 where n[log2n]=nqx or nqy
78 */
79 c = c>>1;
80 nx = nx<<1;
81 ny = ny<<1;
82 if(nfx <= c)
83 nx--;
84 else
85 nfx -= c;
86 if(nfy <= c)
87 ny--;
88 else
89 nfy -= c;
90 qtree_expand(infile, scratch, nx, ny, scratch);
91 }
92
93 /*
94 * copy last set of 4-bit codes to bitplane bit of array a
95 */
96 qtree_bitins(scratch, nqx, nqy, a, n, bit);
97 }
98 }
99 free(scratch);
100 }
101
102 /*
103 * do one quadtree expansion step on array a[(nqx+1)/2,(nqy+1)/2]
104 * results put into b[nqx,nqy] (which may be the same as a)
105 */
106 static
107 void
qtree_expand(Biobuf * infile,uchar * a,int nx,int ny,uchar * b)108 qtree_expand(Biobuf *infile, uchar *a, int nx, int ny, uchar *b)
109 {
110 uchar *b1;
111
112 /*
113 * first copy a to b, expanding each 4-bit value
114 */
115 qtree_copy(a, nx, ny, b, ny);
116
117 /*
118 * now read new 4-bit values into b for each non-zero element
119 */
120 b1 = &b[nx*ny];
121 while(b1 > b) {
122 b1--;
123 if(*b1 != 0)
124 *b1 = input_huffman(infile);
125 }
126 }
127
128 /*
129 * copy 4-bit values from a[(nx+1)/2,(ny+1)/2] to b[nx,ny], expanding
130 * each value to 2x2 pixels
131 * a,b may be same array
132 */
133 static
134 void
qtree_copy(uchar * a,int nx,int ny,uchar * b,int n)135 qtree_copy(uchar *a, int nx, int ny, uchar *b, int n)
136 {
137 int i, j, k, nx2, ny2;
138 int s00, s10;
139
140 /*
141 * first copy 4-bit values to b
142 * start at end in case a,b are same array
143 */
144 nx2 = (nx+1)/2;
145 ny2 = (ny+1)/2;
146 k = ny2*(nx2-1) + ny2-1; /* k is index of a[i,j] */
147 for (i = nx2-1; i >= 0; i--) {
148 s00 = 2*(n*i+ny2-1); /* s00 is index of b[2*i,2*j] */
149 for (j = ny2-1; j >= 0; j--) {
150 b[s00] = a[k];
151 k -= 1;
152 s00 -= 2;
153 }
154 }
155
156 /*
157 * now expand each 2x2 block
158 */
159 for(i = 0; i<nx-1; i += 2) {
160 s00 = n*i; /* s00 is index of b[i,j] */
161 s10 = s00+n; /* s10 is index of b[i+1,j] */
162 for(j = 0; j<ny-1; j += 2) {
163 b[s10+1] = b[s00] & 1;
164 b[s10 ] = (b[s00]>>1) & 1;
165 b[s00+1] = (b[s00]>>2) & 1;
166 b[s00 ] = (b[s00]>>3) & 1;
167 s00 += 2;
168 s10 += 2;
169 }
170 if(j < ny) {
171 /*
172 * row size is odd, do last element in row
173 * s00+1, s10+1 are off edge
174 */
175 b[s10 ] = (b[s00]>>1) & 1;
176 b[s00 ] = (b[s00]>>3) & 1;
177 }
178 }
179 if(i < nx) {
180 /*
181 * column size is odd, do last row
182 * s10, s10+1 are off edge
183 */
184 s00 = n*i;
185 for (j = 0; j<ny-1; j += 2) {
186 b[s00+1] = (b[s00]>>2) & 1;
187 b[s00 ] = (b[s00]>>3) & 1;
188 s00 += 2;
189 }
190 if(j < ny) {
191 /*
192 * both row and column size are odd, do corner element
193 * s00+1, s10, s10+1 are off edge
194 */
195 b[s00 ] = (b[s00]>>3) & 1;
196 }
197 }
198 }
199
200 /*
201 * Copy 4-bit values from a[(nx+1)/2,(ny+1)/2] to b[nx,ny], expanding
202 * each value to 2x2 pixels and inserting into bitplane BIT of B.
203 * A,B may NOT be same array (it wouldn't make sense to be inserting
204 * bits into the same array anyway.)
205 */
206 static
207 void
qtree_bitins(uchar * a,int nx,int ny,Pix * b,int n,int bit)208 qtree_bitins(uchar *a, int nx, int ny, Pix *b, int n, int bit)
209 {
210 int i, j;
211 Pix *s00, *s10;
212 Pix px;
213
214 /*
215 * expand each 2x2 block
216 */
217 for(i=0; i<nx-1; i+=2) {
218 s00 = &b[n*i]; /* s00 is index of b[i,j] */
219 s10 = s00+n; /* s10 is index of b[i+1,j] */
220 for(j=0; j<ny-1; j+=2) {
221 px = *a++;
222 s10[1] |= ( px & 1) << bit;
223 s10[0] |= ((px>>1) & 1) << bit;
224 s00[1] |= ((px>>2) & 1) << bit;
225 s00[0] |= ((px>>3) & 1) << bit;
226 s00 += 2;
227 s10 += 2;
228 }
229 if(j < ny) {
230 /*
231 * row size is odd, do last element in row
232 * s00+1, s10+1 are off edge
233 */
234 px = *a++;
235 s10[0] |= ((px>>1) & 1) << bit;
236 s00[0] |= ((px>>3) & 1) << bit;
237 }
238 }
239 if(i < nx) {
240 /*
241 * column size is odd, do last row
242 * s10, s10+1 are off edge
243 */
244 s00 = &b[n*i];
245 for(j=0; j<ny-1; j+=2) {
246 px = *a++;
247 s00[1] |= ((px>>2) & 1) << bit;
248 s00[0] |= ((px>>3) & 1) << bit;
249 s00 += 2;
250 }
251 if(j < ny) {
252 /*
253 * both row and column size are odd, do corner element
254 * s00+1, s10, s10+1 are off edge
255 */
256 s00[0] |= ((*a>>3) & 1) << bit;
257 }
258 }
259 }
260
261 static
262 void
read_bdirect(Biobuf * infile,Pix * a,int n,int nqx,int nqy,uchar * scratch,int bit)263 read_bdirect(Biobuf *infile, Pix *a, int n, int nqx, int nqy, uchar *scratch, int bit)
264 {
265 int i;
266
267 /*
268 * read bit image packed 4 pixels/nybble
269 */
270 for(i = 0; i < ((nqx+1)/2) * ((nqy+1)/2); i++) {
271 scratch[i] = input_nybble(infile);
272 }
273
274 /*
275 * insert in bitplane BIT of image A
276 */
277 qtree_bitins(scratch, nqx, nqy, a, n, bit);
278 }
279