qtree.c (5811B)
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 }