1 #include <limits.h>
2
3 static void _t2(fwd_xform, Int, DIMS)(Int* p);
4
5 /* private functions ------------------------------------------------------- */
6
7 /* pad partial block of width n <= 4 and stride s */
8 static void
_t1(pad_block,Scalar)9 _t1(pad_block, Scalar)(Scalar* p, uint n, uint s)
10 {
11 switch (n) {
12 case 0:
13 p[0 * s] = 0;
14 /* FALLTHROUGH */
15 case 1:
16 p[1 * s] = p[0 * s];
17 /* FALLTHROUGH */
18 case 2:
19 p[2 * s] = p[1 * s];
20 /* FALLTHROUGH */
21 case 3:
22 p[3 * s] = p[0 * s];
23 /* FALLTHROUGH */
24 default:
25 break;
26 }
27 }
28
29 /* forward lifting transform of 4-vector */
30 static void
_t1(fwd_lift,Int)31 _t1(fwd_lift, Int)(Int* p, uint s)
32 {
33 Int x, y, z, w;
34 x = *p; p += s;
35 y = *p; p += s;
36 z = *p; p += s;
37 w = *p; p += s;
38
39 /*
40 ** non-orthogonal transform
41 ** ( 4 4 4 4) (x)
42 ** 1/16 * ( 5 1 -1 -5) (y)
43 ** (-4 4 4 -4) (z)
44 ** (-2 6 -6 2) (w)
45 */
46 x += w; x >>= 1; w -= x;
47 z += y; z >>= 1; y -= z;
48 x += z; x >>= 1; z -= x;
49 w += y; w >>= 1; y -= w;
50 w += y >> 1; y -= w >> 1;
51
52 p -= s; *p = w;
53 p -= s; *p = z;
54 p -= s; *p = y;
55 p -= s; *p = x;
56 }
57
58 /* map two's complement signed integer to negabinary unsigned integer */
59 static UInt
_t1(int2uint,Int)60 _t1(int2uint, Int)(Int x)
61 {
62 return ((UInt)x + NBMASK) ^ NBMASK;
63 }
64
65 /* reorder signed coefficients and convert to unsigned integer */
66 static void
_t1(fwd_order,Int)67 _t1(fwd_order, Int)(UInt* ublock, const Int* iblock, const uchar* perm, uint n)
68 {
69 do
70 *ublock++ = _t1(int2uint, Int)(iblock[*perm++]);
71 while (--n);
72 }
73
74 /* compress sequence of size unsigned integers */
75 static uint
_t1(encode_ints,UInt)76 _t1(encode_ints, UInt)(bitstream* restrict_ stream, uint maxbits, uint maxprec, const UInt* restrict_ data, uint size)
77 {
78 /* make a copy of bit stream to avoid aliasing */
79 bitstream s = *stream;
80 uint intprec = CHAR_BIT * (uint)sizeof(UInt);
81 uint kmin = intprec > maxprec ? intprec - maxprec : 0;
82 uint bits = maxbits;
83 uint i, k, m, n;
84 uint64 x;
85
86 /* encode one bit plane at a time from MSB to LSB */
87 for (k = intprec, n = 0; bits && k-- > kmin;) {
88 /* step 1: extract bit plane #k to x */
89 x = 0;
90 for (i = 0; i < size; i++)
91 x += (uint64)((data[i] >> k) & 1u) << i;
92 /* step 2: encode first n bits of bit plane */
93 m = MIN(n, bits);
94 bits -= m;
95 x = stream_write_bits(&s, x, m);
96 /* step 3: unary run-length encode remainder of bit plane */
97 for (; n < size && bits && (bits--, stream_write_bit(&s, !!x)); x >>= 1, n++)
98 for (; n < size - 1 && bits && (bits--, !stream_write_bit(&s, x & 1u)); x >>= 1, n++)
99 ;
100 }
101
102 *stream = s;
103 return maxbits - bits;
104 }
105
106 /* compress sequence of size > 64 unsigned integers */
107 static uint
_t1(encode_many_ints,UInt)108 _t1(encode_many_ints, UInt)(bitstream* restrict_ stream, uint maxbits, uint maxprec, const UInt* restrict_ data, uint size)
109 {
110 /* make a copy of bit stream to avoid aliasing */
111 bitstream s = *stream;
112 uint intprec = CHAR_BIT * (uint)sizeof(UInt);
113 uint kmin = intprec > maxprec ? intprec - maxprec : 0;
114 uint bits = maxbits;
115 uint i, k, m, n, c;
116
117 /* encode one bit plane at a time from MSB to LSB */
118 for (k = intprec, n = 0; bits && k-- > kmin;) {
119 /* step 1: encode first n bits of bit plane #k */
120 m = MIN(n, bits);
121 bits -= m;
122 for (i = 0; i < m; i++)
123 stream_write_bit(&s, (data[i] >> k) & 1u);
124 /* step 2: count remaining one-bits in bit plane */
125 c = 0;
126 for (i = m; i < size; i++)
127 c += (data[i] >> k) & 1u;
128 /* step 3: unary run-length encode remainder of bit plane */
129 for (; n < size && bits && (--bits, stream_write_bit(&s, !!c)); c--, n++)
130 for (; n < size - 1 && bits && (--bits, !stream_write_bit(&s, (data[n] >> k) & 1u)); n++)
131 ;
132 }
133
134 *stream = s;
135 return maxbits - bits;
136 }
137
138 /* encode block of integers */
139 static uint
_t2(encode_block,Int,DIMS)140 _t2(encode_block, Int, DIMS)(bitstream* stream, int minbits, int maxbits, int maxprec, Int* iblock)
141 {
142 int bits;
143 cache_align_(UInt ublock[BLOCK_SIZE]);
144 /* perform decorrelating transform */
145 _t2(fwd_xform, Int, DIMS)(iblock);
146 /* reorder signed coefficients and convert to unsigned integer */
147 _t1(fwd_order, Int)(ublock, iblock, PERM, BLOCK_SIZE);
148 /* encode integer coefficients */
149 if (BLOCK_SIZE <= 64)
150 bits = _t1(encode_ints, UInt)(stream, maxbits, maxprec, ublock, BLOCK_SIZE);
151 else
152 bits = _t1(encode_many_ints, UInt)(stream, maxbits, maxprec, ublock, BLOCK_SIZE);
153 /* write at least minbits bits by padding with zeros */
154 if (bits < minbits) {
155 stream_pad(stream, minbits - bits);
156 bits = minbits;
157 }
158 return bits;
159 }
160