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
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
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
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
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
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 }