diff options
author | Dave Bryant <bryant@rockbox.org> | 2005-07-04 06:38:00 +0000 |
---|---|---|
committer | Dave Bryant <bryant@rockbox.org> | 2005-07-04 06:38:00 +0000 |
commit | dacbc16d5b2c2a113eab6b9295db12795d98e2cc (patch) | |
tree | 6040249a9776880f02d478532028f41065a65451 /apps/codecs/libwavpack/words.c | |
parent | 1d5f07b0a654ca0ee0b6f4785388801ed809af33 (diff) | |
download | rockbox-dacbc16d5b2c2a113eab6b9295db12795d98e2cc.tar.gz rockbox-dacbc16d5b2c2a113eab6b9295db12795d98e2cc.zip |
Added lossless encoding to WavPack library. Also made a few changes to
decoding stuff in preparation for future optimization and eliminated all tabs.
git-svn-id: svn://svn.rockbox.org/rockbox/trunk@7009 a1c6a512-1295-4272-9138-f99709370657
Diffstat (limited to 'apps/codecs/libwavpack/words.c')
-rw-r--r-- | apps/codecs/libwavpack/words.c | 798 |
1 files changed, 529 insertions, 269 deletions
diff --git a/apps/codecs/libwavpack/words.c b/apps/codecs/libwavpack/words.c index 8e2fc427a6..75d8a86af7 100644 --- a/apps/codecs/libwavpack/words.c +++ b/apps/codecs/libwavpack/words.c | |||
@@ -29,7 +29,7 @@ | |||
29 | 29 | ||
30 | //////////////////////////////// local macros ///////////////////////////////// | 30 | //////////////////////////////// local macros ///////////////////////////////// |
31 | 31 | ||
32 | #define LIMIT_ONES 16 // maximum consecutive 1s sent for "div" data | 32 | #define LIMIT_ONES 16 // maximum consecutive 1s sent for "div" data |
33 | 33 | ||
34 | // these control the time constant "slow_level" which is used for hybrid mode | 34 | // these control the time constant "slow_level" which is used for hybrid mode |
35 | // that controls bitrate as a function of residual level (HYBRID_BITRATE). | 35 | // that controls bitrate as a function of residual level (HYBRID_BITRATE). |
@@ -37,9 +37,9 @@ | |||
37 | #define SLO ((1 << (SLS - 1))) | 37 | #define SLO ((1 << (SLS - 1))) |
38 | 38 | ||
39 | // these control the time constant of the 3 median level breakpoints | 39 | // these control the time constant of the 3 median level breakpoints |
40 | #define DIV0 128 // 5/7 of samples | 40 | #define DIV0 128 // 5/7 of samples |
41 | #define DIV1 64 // 10/49 of samples | 41 | #define DIV1 64 // 10/49 of samples |
42 | #define DIV2 32 // 20/343 of samples | 42 | #define DIV2 32 // 20/343 of samples |
43 | 43 | ||
44 | // this macro retrieves the specified median breakpoint (without frac; min = 1) | 44 | // this macro retrieves the specified median breakpoint (without frac; min = 1) |
45 | #define GET_MED(med) (((c->median [med]) >> 4) + 1) | 45 | #define GET_MED(med) (((c->median [med]) >> 4) + 1) |
@@ -66,23 +66,45 @@ | |||
66 | 66 | ||
67 | ///////////////////////////// local table storage //////////////////////////// | 67 | ///////////////////////////// local table storage //////////////////////////// |
68 | 68 | ||
69 | const ulong bitset [] = { | ||
70 | 1L << 0, 1L << 1, 1L << 2, 1L << 3, | ||
71 | 1L << 4, 1L << 5, 1L << 6, 1L << 7, | ||
72 | 1L << 8, 1L << 9, 1L << 10, 1L << 11, | ||
73 | 1L << 12, 1L << 13, 1L << 14, 1L << 15, | ||
74 | 1L << 16, 1L << 17, 1L << 18, 1L << 19, | ||
75 | 1L << 20, 1L << 21, 1L << 22, 1L << 23, | ||
76 | 1L << 24, 1L << 25, 1L << 26, 1L << 27, | ||
77 | 1L << 28, 1L << 29, 1L << 30, 1L << 31 | ||
78 | }; | ||
79 | |||
80 | const ulong bitmask [] = { | ||
81 | (1L << 0) - 1, (1L << 1) - 1, (1L << 2) - 1, (1L << 3) - 1, | ||
82 | (1L << 4) - 1, (1L << 5) - 1, (1L << 6) - 1, (1L << 7) - 1, | ||
83 | (1L << 8) - 1, (1L << 9) - 1, (1L << 10) - 1, (1L << 11) - 1, | ||
84 | (1L << 12) - 1, (1L << 13) - 1, (1L << 14) - 1, (1L << 15) - 1, | ||
85 | (1L << 16) - 1, (1L << 17) - 1, (1L << 18) - 1, (1L << 19) - 1, | ||
86 | (1L << 20) - 1, (1L << 21) - 1, (1L << 22) - 1, (1L << 23) - 1, | ||
87 | (1L << 24) - 1, (1L << 25) - 1, (1L << 26) - 1, (1L << 27) - 1, | ||
88 | (1L << 28) - 1, (1L << 29) - 1, (1L << 30) - 1, 0x7fffffff | ||
89 | }; | ||
90 | |||
69 | const char nbits_table [] = { | 91 | const char nbits_table [] = { |
70 | 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, // 0 - 15 | 92 | 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, // 0 - 15 |
71 | 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, // 16 - 31 | 93 | 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, // 16 - 31 |
72 | 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, // 32 - 47 | 94 | 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, // 32 - 47 |
73 | 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, // 48 - 63 | 95 | 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, // 48 - 63 |
74 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 64 - 79 | 96 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 64 - 79 |
75 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 80 - 95 | 97 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 80 - 95 |
76 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 96 - 111 | 98 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 96 - 111 |
77 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 112 - 127 | 99 | 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 112 - 127 |
78 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 128 - 143 | 100 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 128 - 143 |
79 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 144 - 159 | 101 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 144 - 159 |
80 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 160 - 175 | 102 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 160 - 175 |
81 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 176 - 191 | 103 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 176 - 191 |
82 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 192 - 207 | 104 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 192 - 207 |
83 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 208 - 223 | 105 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 208 - 223 |
84 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 224 - 239 | 106 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, // 224 - 239 |
85 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 // 240 - 255 | 107 | 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 // 240 - 255 |
86 | }; | 108 | }; |
87 | 109 | ||
88 | static const uchar log2_table [] = { | 110 | static const uchar log2_table [] = { |
@@ -136,6 +158,11 @@ static const char ones_count_table [] = { | |||
136 | 158 | ||
137 | ///////////////////////////// executable code //////////////////////////////// | 159 | ///////////////////////////// executable code //////////////////////////////// |
138 | 160 | ||
161 | void init_words (WavpackStream *wps) | ||
162 | { | ||
163 | CLEAR (wps->w); | ||
164 | } | ||
165 | |||
139 | static int mylog2 (unsigned long avalue); | 166 | static int mylog2 (unsigned long avalue); |
140 | 167 | ||
141 | // Read the median log2 values from the specifed metadata structure, convert | 168 | // Read the median log2 values from the specifed metadata structure, convert |
@@ -147,21 +174,55 @@ int read_entropy_vars (WavpackStream *wps, WavpackMetadata *wpmd) | |||
147 | uchar *byteptr = wpmd->data; | 174 | uchar *byteptr = wpmd->data; |
148 | 175 | ||
149 | if (wpmd->byte_length != ((wps->wphdr.flags & MONO_FLAG) ? 6 : 12)) | 176 | if (wpmd->byte_length != ((wps->wphdr.flags & MONO_FLAG) ? 6 : 12)) |
150 | return FALSE; | 177 | return FALSE; |
151 | 178 | ||
152 | wps->w.c [0].median [0] = exp2s (byteptr [0] + (byteptr [1] << 8)); | 179 | wps->w.c [0].median [0] = exp2s (byteptr [0] + (byteptr [1] << 8)); |
153 | wps->w.c [0].median [1] = exp2s (byteptr [2] + (byteptr [3] << 8)); | 180 | wps->w.c [0].median [1] = exp2s (byteptr [2] + (byteptr [3] << 8)); |
154 | wps->w.c [0].median [2] = exp2s (byteptr [4] + (byteptr [5] << 8)); | 181 | wps->w.c [0].median [2] = exp2s (byteptr [4] + (byteptr [5] << 8)); |
155 | 182 | ||
156 | if (!(wps->wphdr.flags & MONO_FLAG)) { | 183 | if (!(wps->wphdr.flags & MONO_FLAG)) { |
157 | wps->w.c [1].median [0] = exp2s (byteptr [6] + (byteptr [7] << 8)); | 184 | wps->w.c [1].median [0] = exp2s (byteptr [6] + (byteptr [7] << 8)); |
158 | wps->w.c [1].median [1] = exp2s (byteptr [8] + (byteptr [9] << 8)); | 185 | wps->w.c [1].median [1] = exp2s (byteptr [8] + (byteptr [9] << 8)); |
159 | wps->w.c [1].median [2] = exp2s (byteptr [10] + (byteptr [11] << 8)); | 186 | wps->w.c [1].median [2] = exp2s (byteptr [10] + (byteptr [11] << 8)); |
160 | } | 187 | } |
161 | 188 | ||
162 | return TRUE; | 189 | return TRUE; |
163 | } | 190 | } |
164 | 191 | ||
192 | // Allocates the correct space in the metadata structure and writes the | ||
193 | // current median values to it. Values are converted from 32-bit unsigned | ||
194 | // to our internal 16-bit mylog2 values, and read_entropy_vars () is called | ||
195 | // to read the values back because we must compensate for the loss through | ||
196 | // the log function. | ||
197 | |||
198 | void write_entropy_vars (WavpackStream *wps, WavpackMetadata *wpmd) | ||
199 | { | ||
200 | uchar *byteptr; | ||
201 | int temp; | ||
202 | |||
203 | byteptr = wpmd->data = wpmd->temp_data; | ||
204 | wpmd->id = ID_ENTROPY_VARS; | ||
205 | |||
206 | *byteptr++ = temp = mylog2 (wps->w.c [0].median [0]); | ||
207 | *byteptr++ = temp >> 8; | ||
208 | *byteptr++ = temp = mylog2 (wps->w.c [0].median [1]); | ||
209 | *byteptr++ = temp >> 8; | ||
210 | *byteptr++ = temp = mylog2 (wps->w.c [0].median [2]); | ||
211 | *byteptr++ = temp >> 8; | ||
212 | |||
213 | if (!(wps->wphdr.flags & MONO_FLAG)) { | ||
214 | *byteptr++ = temp = mylog2 (wps->w.c [1].median [0]); | ||
215 | *byteptr++ = temp >> 8; | ||
216 | *byteptr++ = temp = mylog2 (wps->w.c [1].median [1]); | ||
217 | *byteptr++ = temp >> 8; | ||
218 | *byteptr++ = temp = mylog2 (wps->w.c [1].median [2]); | ||
219 | *byteptr++ = temp >> 8; | ||
220 | } | ||
221 | |||
222 | wpmd->byte_length = byteptr - (uchar *) wpmd->data; | ||
223 | read_entropy_vars (wps, wpmd); | ||
224 | } | ||
225 | |||
165 | // Read the hybrid related values from the specifed metadata structure, convert | 226 | // Read the hybrid related values from the specifed metadata structure, convert |
166 | // them back to their internal formats and store them. The extended profile | 227 | // them back to their internal formats and store them. The extended profile |
167 | // stuff is not implemented yet, so return an error if we get more data than | 228 | // stuff is not implemented yet, so return an error if we get more data than |
@@ -173,37 +234,37 @@ int read_hybrid_profile (WavpackStream *wps, WavpackMetadata *wpmd) | |||
173 | uchar *endptr = byteptr + wpmd->byte_length; | 234 | uchar *endptr = byteptr + wpmd->byte_length; |
174 | 235 | ||
175 | if (wps->wphdr.flags & HYBRID_BITRATE) { | 236 | if (wps->wphdr.flags & HYBRID_BITRATE) { |
176 | wps->w.c [0].slow_level = exp2s (byteptr [0] + (byteptr [1] << 8)); | 237 | wps->w.c [0].slow_level = exp2s (byteptr [0] + (byteptr [1] << 8)); |
177 | byteptr += 2; | 238 | byteptr += 2; |
178 | 239 | ||
179 | if (!(wps->wphdr.flags & MONO_FLAG)) { | 240 | if (!(wps->wphdr.flags & MONO_FLAG)) { |
180 | wps->w.c [1].slow_level = exp2s (byteptr [0] + (byteptr [1] << 8)); | 241 | wps->w.c [1].slow_level = exp2s (byteptr [0] + (byteptr [1] << 8)); |
181 | byteptr += 2; | 242 | byteptr += 2; |
182 | } | 243 | } |
183 | } | 244 | } |
184 | 245 | ||
185 | wps->w.bitrate_acc [0] = (long)(byteptr [0] + (byteptr [1] << 8)) << 16; | 246 | wps->w.bitrate_acc [0] = (long)(byteptr [0] + (byteptr [1] << 8)) << 16; |
186 | byteptr += 2; | 247 | byteptr += 2; |
187 | 248 | ||
188 | if (!(wps->wphdr.flags & MONO_FLAG)) { | 249 | if (!(wps->wphdr.flags & MONO_FLAG)) { |
189 | wps->w.bitrate_acc [1] = (long)(byteptr [0] + (byteptr [1] << 8)) << 16; | 250 | wps->w.bitrate_acc [1] = (long)(byteptr [0] + (byteptr [1] << 8)) << 16; |
190 | byteptr += 2; | 251 | byteptr += 2; |
191 | } | 252 | } |
192 | 253 | ||
193 | if (byteptr < endptr) { | 254 | if (byteptr < endptr) { |
194 | wps->w.bitrate_delta [0] = exp2s ((short)(byteptr [0] + (byteptr [1] << 8))); | 255 | wps->w.bitrate_delta [0] = exp2s ((short)(byteptr [0] + (byteptr [1] << 8))); |
195 | byteptr += 2; | 256 | byteptr += 2; |
196 | 257 | ||
197 | if (!(wps->wphdr.flags & MONO_FLAG)) { | 258 | if (!(wps->wphdr.flags & MONO_FLAG)) { |
198 | wps->w.bitrate_delta [1] = exp2s ((short)(byteptr [0] + (byteptr [1] << 8))); | 259 | wps->w.bitrate_delta [1] = exp2s ((short)(byteptr [0] + (byteptr [1] << 8))); |
199 | byteptr += 2; | 260 | byteptr += 2; |
200 | } | 261 | } |
201 | 262 | ||
202 | if (byteptr < endptr) | 263 | if (byteptr < endptr) |
203 | return FALSE; | 264 | return FALSE; |
204 | } | 265 | } |
205 | else | 266 | else |
206 | wps->w.bitrate_delta [0] = wps->w.bitrate_delta [1] = 0; | 267 | wps->w.bitrate_delta [0] = wps->w.bitrate_delta [1] = 0; |
207 | 268 | ||
208 | return TRUE; | 269 | return TRUE; |
209 | } | 270 | } |
@@ -214,60 +275,60 @@ int read_hybrid_profile (WavpackStream *wps, WavpackMetadata *wpmd) | |||
214 | // currently implemented) this is calculated from the slow_level values and the | 275 | // currently implemented) this is calculated from the slow_level values and the |
215 | // bitrate accumulators. Note that the bitrate accumulators can be changing. | 276 | // bitrate accumulators. Note that the bitrate accumulators can be changing. |
216 | 277 | ||
217 | static void update_error_limit (WavpackStream *wps) | 278 | void update_error_limit (struct words_data *w, ulong flags) |
218 | { | 279 | { |
219 | int bitrate_0 = (wps->w.bitrate_acc [0] += wps->w.bitrate_delta [0]) >> 16; | 280 | int bitrate_0 = (w->bitrate_acc [0] += w->bitrate_delta [0]) >> 16; |
220 | 281 | ||
221 | if (wps->wphdr.flags & MONO_FLAG) { | 282 | if (flags & MONO_FLAG) { |
222 | if (wps->wphdr.flags & HYBRID_BITRATE) { | 283 | if (flags & HYBRID_BITRATE) { |
223 | int slow_log_0 = (wps->w.c [0].slow_level + SLO) >> SLS; | 284 | int slow_log_0 = (w->c [0].slow_level + SLO) >> SLS; |
224 | 285 | ||
225 | if (slow_log_0 - bitrate_0 > -0x100) | 286 | if (slow_log_0 - bitrate_0 > -0x100) |
226 | wps->w.c [0].error_limit = exp2s (slow_log_0 - bitrate_0 + 0x100); | 287 | w->c [0].error_limit = exp2s (slow_log_0 - bitrate_0 + 0x100); |
227 | else | 288 | else |
228 | wps->w.c [0].error_limit = 0; | 289 | w->c [0].error_limit = 0; |
229 | } | 290 | } |
230 | else | 291 | else |
231 | wps->w.c [0].error_limit = exp2s (bitrate_0); | 292 | w->c [0].error_limit = exp2s (bitrate_0); |
232 | } | 293 | } |
233 | else { | 294 | else { |
234 | int bitrate_1 = (wps->w.bitrate_acc [1] += wps->w.bitrate_delta [1]) >> 16; | 295 | int bitrate_1 = (w->bitrate_acc [1] += w->bitrate_delta [1]) >> 16; |
235 | 296 | ||
236 | if (wps->wphdr.flags & HYBRID_BITRATE) { | 297 | if (flags & HYBRID_BITRATE) { |
237 | int slow_log_0 = (wps->w.c [0].slow_level + SLO) >> SLS; | 298 | int slow_log_0 = (w->c [0].slow_level + SLO) >> SLS; |
238 | int slow_log_1 = (wps->w.c [1].slow_level + SLO) >> SLS; | 299 | int slow_log_1 = (w->c [1].slow_level + SLO) >> SLS; |
239 | 300 | ||
240 | if (wps->wphdr.flags & HYBRID_BALANCE) { | 301 | if (flags & HYBRID_BALANCE) { |
241 | int balance = (slow_log_1 - slow_log_0 + bitrate_1 + 1) >> 1; | 302 | int balance = (slow_log_1 - slow_log_0 + bitrate_1 + 1) >> 1; |
242 | 303 | ||
243 | if (balance > bitrate_0) { | 304 | if (balance > bitrate_0) { |
244 | bitrate_1 = bitrate_0 * 2; | 305 | bitrate_1 = bitrate_0 * 2; |
245 | bitrate_0 = 0; | 306 | bitrate_0 = 0; |
246 | } | 307 | } |
247 | else if (-balance > bitrate_0) { | 308 | else if (-balance > bitrate_0) { |
248 | bitrate_0 = bitrate_0 * 2; | 309 | bitrate_0 = bitrate_0 * 2; |
249 | bitrate_1 = 0; | 310 | bitrate_1 = 0; |
250 | } | 311 | } |
251 | else { | 312 | else { |
252 | bitrate_1 = bitrate_0 + balance; | 313 | bitrate_1 = bitrate_0 + balance; |
253 | bitrate_0 = bitrate_0 - balance; | 314 | bitrate_0 = bitrate_0 - balance; |
254 | } | 315 | } |
255 | } | 316 | } |
256 | 317 | ||
257 | if (slow_log_0 - bitrate_0 > -0x100) | 318 | if (slow_log_0 - bitrate_0 > -0x100) |
258 | wps->w.c [0].error_limit = exp2s (slow_log_0 - bitrate_0 + 0x100); | 319 | w->c [0].error_limit = exp2s (slow_log_0 - bitrate_0 + 0x100); |
259 | else | 320 | else |
260 | wps->w.c [0].error_limit = 0; | 321 | w->c [0].error_limit = 0; |
261 | 322 | ||
262 | if (slow_log_1 - bitrate_1 > -0x100) | 323 | if (slow_log_1 - bitrate_1 > -0x100) |
263 | wps->w.c [1].error_limit = exp2s (slow_log_1 - bitrate_1 + 0x100); | 324 | w->c [1].error_limit = exp2s (slow_log_1 - bitrate_1 + 0x100); |
264 | else | 325 | else |
265 | wps->w.c [1].error_limit = 0; | 326 | w->c [1].error_limit = 0; |
266 | } | 327 | } |
267 | else { | 328 | else { |
268 | wps->w.c [0].error_limit = exp2s (bitrate_0); | 329 | w->c [0].error_limit = exp2s (bitrate_0); |
269 | wps->w.c [1].error_limit = exp2s (bitrate_1); | 330 | w->c [1].error_limit = exp2s (bitrate_1); |
270 | } | 331 | } |
271 | } | 332 | } |
272 | } | 333 | } |
273 | 334 | ||
@@ -281,168 +342,171 @@ static ulong read_code (Bitstream *bs, ulong maxcode); | |||
281 | // of WORD_EOF indicates that the end of the bitstream was reached (all 1s) or | 342 | // of WORD_EOF indicates that the end of the bitstream was reached (all 1s) or |
282 | // some other error occurred. | 343 | // some other error occurred. |
283 | 344 | ||
284 | long get_words (WavpackStream *wps, int nchans, int nsamples, long *buffer) | 345 | long get_words (long *buffer, int nsamples, ulong flags, |
346 | struct words_data *w, Bitstream *bs) | ||
285 | { | 347 | { |
286 | ulong ones_count, low, mid, high; | 348 | register struct entropy_data *c = w->c; |
287 | register struct entropy_data *c; | 349 | int csamples; |
288 | long *bptr = buffer; | 350 | |
289 | 351 | if (!(flags & MONO_FLAG)) | |
290 | nsamples *= nchans; | 352 | nsamples *= 2; |
291 | 353 | ||
292 | while (nsamples--) { | 354 | for (csamples = 0; csamples < nsamples; ++csamples) { |
293 | 355 | ulong ones_count, low, mid, high; | |
294 | c = wps->w.c + ((nchans == 1) ? 0 : (~nsamples & 1)); | 356 | |
295 | 357 | if (!(flags & MONO_FLAG)) | |
296 | if (!(wps->w.c [0].median [0] & ~1) && !wps->w.holding_zero && !wps->w.holding_one && !(wps->w.c [1].median [0] & ~1)) { | 358 | c = w->c + (csamples & 1); |
297 | ulong mask; | 359 | |
298 | int cbits; | 360 | if (!(w->c [0].median [0] & ~1) && !w->holding_zero && !w->holding_one && !(w->c [1].median [0] & ~1)) { |
299 | 361 | ulong mask; | |
300 | if (wps->w.zeros_acc) { | 362 | int cbits; |
301 | if (--wps->w.zeros_acc) { | 363 | |
302 | c->slow_level -= (c->slow_level + SLO) >> SLS; | 364 | if (w->zeros_acc) { |
303 | *bptr++ = 0; | 365 | if (--w->zeros_acc) { |
304 | continue; | 366 | c->slow_level -= (c->slow_level + SLO) >> SLS; |
305 | } | 367 | *buffer++ = 0; |
306 | } | 368 | continue; |
307 | else { | 369 | } |
308 | for (cbits = 0; cbits < 33 && getbit (&wps->wvbits); ++cbits); | 370 | } |
309 | 371 | else { | |
310 | if (cbits == 33) | 372 | for (cbits = 0; cbits < 33 && getbit (bs); ++cbits); |
311 | break; | 373 | |
312 | 374 | if (cbits == 33) | |
313 | if (cbits < 2) | 375 | break; |
314 | wps->w.zeros_acc = cbits; | 376 | |
315 | else { | 377 | if (cbits < 2) |
316 | for (mask = 1, wps->w.zeros_acc = 0; --cbits; mask <<= 1) | 378 | w->zeros_acc = cbits; |
317 | if (getbit (&wps->wvbits)) | 379 | else { |
318 | wps->w.zeros_acc |= mask; | 380 | for (mask = 1, w->zeros_acc = 0; --cbits; mask <<= 1) |
319 | 381 | if (getbit (bs)) | |
320 | wps->w.zeros_acc |= mask; | 382 | w->zeros_acc |= mask; |
321 | } | 383 | |
322 | 384 | w->zeros_acc |= mask; | |
323 | if (wps->w.zeros_acc) { | 385 | } |
324 | c->slow_level -= (c->slow_level + SLO) >> SLS; | 386 | |
325 | CLEAR (wps->w.c [0].median); | 387 | if (w->zeros_acc) { |
326 | CLEAR (wps->w.c [1].median); | 388 | c->slow_level -= (c->slow_level + SLO) >> SLS; |
327 | *bptr++ = 0; | 389 | CLEAR (w->c [0].median); |
328 | continue; | 390 | CLEAR (w->c [1].median); |
329 | } | 391 | *buffer++ = 0; |
330 | } | 392 | continue; |
331 | } | 393 | } |
332 | 394 | } | |
333 | if (wps->w.holding_zero) | 395 | } |
334 | ones_count = wps->w.holding_zero = 0; | 396 | |
335 | else { | 397 | if (w->holding_zero) |
336 | int next8; | 398 | ones_count = w->holding_zero = 0; |
337 | 399 | else { | |
338 | if (wps->wvbits.bc < 8) { | 400 | int next8; |
339 | if (++(wps->wvbits.ptr) == wps->wvbits.end) | 401 | |
340 | wps->wvbits.wrap (&wps->wvbits); | 402 | if (bs->bc < 8) { |
341 | 403 | if (++(bs->ptr) == bs->end) | |
342 | next8 = (wps->wvbits.sr |= *(wps->wvbits.ptr) << wps->wvbits.bc) & 0xff; | 404 | bs->wrap (bs); |
343 | wps->wvbits.bc += 8; | 405 | |
344 | } | 406 | next8 = (bs->sr |= *(bs->ptr) << bs->bc) & 0xff; |
345 | else | 407 | bs->bc += 8; |
346 | next8 = wps->wvbits.sr & 0xff; | 408 | } |
347 | 409 | else | |
348 | if (next8 == 0xff) { | 410 | next8 = bs->sr & 0xff; |
349 | wps->wvbits.bc -= 8; | 411 | |
350 | wps->wvbits.sr >>= 8; | 412 | if (next8 == 0xff) { |
351 | 413 | bs->bc -= 8; | |
352 | for (ones_count = 8; ones_count < (LIMIT_ONES + 1) && getbit (&wps->wvbits); ++ones_count); | 414 | bs->sr >>= 8; |
353 | 415 | ||
354 | if (ones_count == (LIMIT_ONES + 1)) | 416 | for (ones_count = 8; ones_count < (LIMIT_ONES + 1) && getbit (bs); ++ones_count); |
355 | break; | 417 | |
356 | 418 | if (ones_count == (LIMIT_ONES + 1)) | |
357 | if (ones_count == LIMIT_ONES) { | 419 | break; |
358 | ulong mask; | 420 | |
359 | int cbits; | 421 | if (ones_count == LIMIT_ONES) { |
360 | 422 | ulong mask; | |
361 | for (cbits = 0; cbits < 33 && getbit (&wps->wvbits); ++cbits); | 423 | int cbits; |
362 | 424 | ||
363 | if (cbits == 33) | 425 | for (cbits = 0; cbits < 33 && getbit (bs); ++cbits); |
364 | break; | 426 | |
365 | 427 | if (cbits == 33) | |
366 | if (cbits < 2) | 428 | break; |
367 | ones_count = cbits; | 429 | |
368 | else { | 430 | if (cbits < 2) |
369 | for (mask = 1, ones_count = 0; --cbits; mask <<= 1) | 431 | ones_count = cbits; |
370 | if (getbit (&wps->wvbits)) | 432 | else { |
371 | ones_count |= mask; | 433 | for (mask = 1, ones_count = 0; --cbits; mask <<= 1) |
372 | 434 | if (getbit (bs)) | |
373 | ones_count |= mask; | 435 | ones_count |= mask; |
374 | } | 436 | |
375 | 437 | ones_count |= mask; | |
376 | ones_count += LIMIT_ONES; | 438 | } |
377 | } | 439 | |
378 | } | 440 | ones_count += LIMIT_ONES; |
379 | else { | 441 | } |
380 | wps->wvbits.bc -= (ones_count = ones_count_table [next8]) + 1; | 442 | } |
381 | wps->wvbits.sr >>= ones_count + 1; | 443 | else { |
382 | } | 444 | bs->bc -= (ones_count = ones_count_table [next8]) + 1; |
383 | 445 | bs->sr >>= ones_count + 1; | |
384 | if (wps->w.holding_one) { | 446 | } |
385 | wps->w.holding_one = ones_count & 1; | 447 | |
386 | ones_count = (ones_count >> 1) + 1; | 448 | if (w->holding_one) { |
387 | } | 449 | w->holding_one = ones_count & 1; |
388 | else { | 450 | ones_count = (ones_count >> 1) + 1; |
389 | wps->w.holding_one = ones_count & 1; | 451 | } |
390 | ones_count >>= 1; | 452 | else { |
391 | } | 453 | w->holding_one = ones_count & 1; |
392 | 454 | ones_count >>= 1; | |
393 | wps->w.holding_zero = ~wps->w.holding_one & 1; | 455 | } |
394 | } | 456 | |
395 | 457 | w->holding_zero = ~w->holding_one & 1; | |
396 | if ((wps->wphdr.flags & HYBRID_FLAG) && (nchans == 1 || (nsamples & 1))) | 458 | } |
397 | update_error_limit (wps); | 459 | |
398 | 460 | if ((flags & HYBRID_FLAG) && ((flags & MONO_FLAG) || !(csamples & 1))) | |
399 | if (ones_count == 0) { | 461 | update_error_limit (w, flags); |
400 | low = 0; | 462 | |
401 | high = GET_MED (0) - 1; | 463 | if (ones_count == 0) { |
402 | DEC_MED0 (); | 464 | low = 0; |
403 | } | 465 | high = GET_MED (0) - 1; |
404 | else { | 466 | DEC_MED0 (); |
405 | low = GET_MED (0); | 467 | } |
406 | INC_MED0 (); | 468 | else { |
407 | 469 | low = GET_MED (0); | |
408 | if (ones_count == 1) { | 470 | INC_MED0 (); |
409 | high = low + GET_MED (1) - 1; | 471 | |
410 | DEC_MED1 (); | 472 | if (ones_count == 1) { |
411 | } | 473 | high = low + GET_MED (1) - 1; |
412 | else { | 474 | DEC_MED1 (); |
413 | low += GET_MED (1); | 475 | } |
414 | INC_MED1 (); | 476 | else { |
415 | 477 | low += GET_MED (1); | |
416 | if (ones_count == 2) { | 478 | INC_MED1 (); |
417 | high = low + GET_MED (2) - 1; | 479 | |
418 | DEC_MED2 (); | 480 | if (ones_count == 2) { |
419 | } | 481 | high = low + GET_MED (2) - 1; |
420 | else { | 482 | DEC_MED2 (); |
421 | low += (ones_count - 2) * GET_MED (2); | 483 | } |
422 | high = low + GET_MED (2) - 1; | 484 | else { |
423 | INC_MED2 (); | 485 | low += (ones_count - 2) * GET_MED (2); |
424 | } | 486 | high = low + GET_MED (2) - 1; |
425 | } | 487 | INC_MED2 (); |
426 | } | 488 | } |
427 | 489 | } | |
428 | mid = (high + low + 1) >> 1; | 490 | } |
429 | 491 | ||
430 | if (!c->error_limit) | 492 | mid = (high + low + 1) >> 1; |
431 | mid = read_code (&wps->wvbits, high - low) + low; | 493 | |
432 | else while (high - low > c->error_limit) { | 494 | if (!c->error_limit) |
433 | if (getbit (&wps->wvbits)) | 495 | mid = read_code (bs, high - low) + low; |
434 | mid = (high + (low = mid) + 1) >> 1; | 496 | else while (high - low > c->error_limit) { |
435 | else | 497 | if (getbit (bs)) |
436 | mid = ((high = mid - 1) + low + 1) >> 1; | 498 | mid = (high + (low = mid) + 1) >> 1; |
437 | } | 499 | else |
438 | 500 | mid = ((high = mid - 1) + low + 1) >> 1; | |
439 | *bptr++ = getbit (&wps->wvbits) ? ~mid : mid; | 501 | } |
440 | 502 | ||
441 | if (wps->wphdr.flags & HYBRID_BITRATE) | 503 | *buffer++ = getbit (bs) ? ~mid : mid; |
442 | c->slow_level = c->slow_level - ((c->slow_level + SLO) >> SLS) + mylog2 (mid); | 504 | |
505 | if (flags & HYBRID_BITRATE) | ||
506 | c->slow_level = c->slow_level - ((c->slow_level + SLO) >> SLS) + mylog2 (mid); | ||
443 | } | 507 | } |
444 | 508 | ||
445 | return nchans == 1 ? (bptr - buffer) : ((bptr - buffer) / 2); | 509 | return (flags & MONO_FLAG) ? csamples : (csamples / 2); |
446 | } | 510 | } |
447 | 511 | ||
448 | // Read a single unsigned value from the specified bitstream with a value | 512 | // Read a single unsigned value from the specified bitstream with a value |
@@ -457,21 +521,195 @@ static ulong read_code (Bitstream *bs, ulong maxcode) | |||
457 | ulong extras = (1L << bitcount) - maxcode - 1, code; | 521 | ulong extras = (1L << bitcount) - maxcode - 1, code; |
458 | 522 | ||
459 | if (!bitcount) | 523 | if (!bitcount) |
460 | return 0; | 524 | return 0; |
461 | 525 | ||
462 | getbits (&code, bitcount - 1, bs); | 526 | getbits (&code, bitcount - 1, bs); |
463 | code &= (1L << (bitcount - 1)) - 1; | 527 | code &= (1L << (bitcount - 1)) - 1; |
464 | 528 | ||
465 | if (code >= extras) { | 529 | if (code >= extras) { |
466 | code = (code << 1) - extras; | 530 | code = (code << 1) - extras; |
467 | 531 | ||
468 | if (getbit (bs)) | 532 | if (getbit (bs)) |
469 | ++code; | 533 | ++code; |
470 | } | 534 | } |
471 | 535 | ||
472 | return code; | 536 | return code; |
473 | } | 537 | } |
474 | 538 | ||
539 | // This function is an optimized version of send_word() that only handles | ||
540 | // lossless (error_limit == 0). It does not return a value because it always | ||
541 | // encodes the exact value passed. | ||
542 | |||
543 | void send_word_lossless (WavpackStream *wps, long value, int chan) | ||
544 | { | ||
545 | register struct words_data *w = &wps->w; | ||
546 | register struct entropy_data *c = w->c + chan; | ||
547 | int sign = (value < 0) ? 1 : 0; | ||
548 | ulong ones_count, low, high; | ||
549 | |||
550 | if (!(wps->w.c [0].median [0] & ~1) && !wps->w.holding_zero && !(wps->w.c [1].median [0] & ~1)) { | ||
551 | if (wps->w.zeros_acc) { | ||
552 | if (value) | ||
553 | flush_word (wps); | ||
554 | else { | ||
555 | wps->w.zeros_acc++; | ||
556 | return; | ||
557 | } | ||
558 | } | ||
559 | else if (value) { | ||
560 | putbit_0 (&wps->wvbits); | ||
561 | } | ||
562 | else { | ||
563 | CLEAR (wps->w.c [0].median); | ||
564 | CLEAR (wps->w.c [1].median); | ||
565 | wps->w.zeros_acc = 1; | ||
566 | return; | ||
567 | } | ||
568 | } | ||
569 | |||
570 | if (sign) | ||
571 | value = ~value; | ||
572 | |||
573 | if ((unsigned long) value < GET_MED (0)) { | ||
574 | ones_count = low = 0; | ||
575 | high = GET_MED (0) - 1; | ||
576 | DEC_MED0 (); | ||
577 | } | ||
578 | else { | ||
579 | low = GET_MED (0); | ||
580 | INC_MED0 (); | ||
581 | |||
582 | if (value - low < GET_MED (1)) { | ||
583 | ones_count = 1; | ||
584 | high = low + GET_MED (1) - 1; | ||
585 | DEC_MED1 (); | ||
586 | } | ||
587 | else { | ||
588 | low += GET_MED (1); | ||
589 | INC_MED1 (); | ||
590 | |||
591 | if (value - low < GET_MED (2)) { | ||
592 | ones_count = 2; | ||
593 | high = low + GET_MED (2) - 1; | ||
594 | DEC_MED2 (); | ||
595 | } | ||
596 | else { | ||
597 | ones_count = 2 + (value - low) / GET_MED (2); | ||
598 | low += (ones_count - 2) * GET_MED (2); | ||
599 | high = low + GET_MED (2) - 1; | ||
600 | INC_MED2 (); | ||
601 | } | ||
602 | } | ||
603 | } | ||
604 | |||
605 | if (wps->w.holding_zero) { | ||
606 | if (ones_count) | ||
607 | wps->w.holding_one++; | ||
608 | |||
609 | flush_word (wps); | ||
610 | |||
611 | if (ones_count) { | ||
612 | wps->w.holding_zero = 1; | ||
613 | ones_count--; | ||
614 | } | ||
615 | else | ||
616 | wps->w.holding_zero = 0; | ||
617 | } | ||
618 | else | ||
619 | wps->w.holding_zero = 1; | ||
620 | |||
621 | wps->w.holding_one = ones_count * 2; | ||
622 | |||
623 | if (high != low) { | ||
624 | ulong maxcode = high - low, code = value - low; | ||
625 | int bitcount = count_bits (maxcode); | ||
626 | ulong extras = bitset [bitcount] - maxcode - 1; | ||
627 | |||
628 | if (code < extras) { | ||
629 | wps->w.pend_data |= code << wps->w.pend_count; | ||
630 | wps->w.pend_count += bitcount - 1; | ||
631 | } | ||
632 | else { | ||
633 | wps->w.pend_data |= ((code + extras) >> 1) << wps->w.pend_count; | ||
634 | wps->w.pend_count += bitcount - 1; | ||
635 | wps->w.pend_data |= ((code + extras) & 1) << wps->w.pend_count++; | ||
636 | } | ||
637 | } | ||
638 | |||
639 | wps->w.pend_data |= ((long) sign << wps->w.pend_count++); | ||
640 | |||
641 | if (!wps->w.holding_zero) | ||
642 | flush_word (wps); | ||
643 | } | ||
644 | |||
645 | // Used by send_word() and send_word_lossless() to actually send most the | ||
646 | // accumulated data onto the bitstream. This is also called directly from | ||
647 | // clients when all words have been sent. | ||
648 | |||
649 | void flush_word (WavpackStream *wps) | ||
650 | { | ||
651 | if (wps->w.zeros_acc) { | ||
652 | int cbits = count_bits (wps->w.zeros_acc); | ||
653 | |||
654 | while (cbits--) { | ||
655 | putbit_1 (&wps->wvbits); | ||
656 | } | ||
657 | |||
658 | putbit_0 (&wps->wvbits); | ||
659 | |||
660 | while (wps->w.zeros_acc > 1) { | ||
661 | putbit (wps->w.zeros_acc & 1, &wps->wvbits); | ||
662 | wps->w.zeros_acc >>= 1; | ||
663 | } | ||
664 | |||
665 | wps->w.zeros_acc = 0; | ||
666 | } | ||
667 | |||
668 | if (wps->w.holding_one) { | ||
669 | if (wps->w.holding_one >= LIMIT_ONES) { | ||
670 | int cbits; | ||
671 | |||
672 | putbits ((1L << LIMIT_ONES) - 1, LIMIT_ONES + 1, &wps->wvbits); | ||
673 | wps->w.holding_one -= LIMIT_ONES; | ||
674 | cbits = count_bits (wps->w.holding_one); | ||
675 | |||
676 | while (cbits--) { | ||
677 | putbit_1 (&wps->wvbits); | ||
678 | } | ||
679 | |||
680 | putbit_0 (&wps->wvbits); | ||
681 | |||
682 | while (wps->w.holding_one > 1) { | ||
683 | putbit (wps->w.holding_one & 1, &wps->wvbits); | ||
684 | wps->w.holding_one >>= 1; | ||
685 | } | ||
686 | |||
687 | wps->w.holding_zero = 0; | ||
688 | } | ||
689 | else | ||
690 | putbits (bitmask [wps->w.holding_one], wps->w.holding_one, &wps->wvbits); | ||
691 | |||
692 | wps->w.holding_one = 0; | ||
693 | } | ||
694 | |||
695 | if (wps->w.holding_zero) { | ||
696 | putbit_0 (&wps->wvbits); | ||
697 | wps->w.holding_zero = 0; | ||
698 | } | ||
699 | |||
700 | if (wps->w.pend_count) { | ||
701 | |||
702 | while (wps->w.pend_count > 24) { | ||
703 | putbit (wps->w.pend_data & 1, &wps->wvbits); | ||
704 | wps->w.pend_data >>= 1; | ||
705 | wps->w.pend_count--; | ||
706 | } | ||
707 | |||
708 | putbits (wps->w.pend_data, wps->w.pend_count, &wps->wvbits); | ||
709 | wps->w.pend_data = wps->w.pend_count = 0; | ||
710 | } | ||
711 | } | ||
712 | |||
475 | // The concept of a base 2 logarithm is used in many parts of WavPack. It is | 713 | // The concept of a base 2 logarithm is used in many parts of WavPack. It is |
476 | // a way of sufficiently accurately representing 32-bit signed and unsigned | 714 | // a way of sufficiently accurately representing 32-bit signed and unsigned |
477 | // values storing only 16 bits (actually fewer). It is also used in the hybrid | 715 | // values storing only 16 bits (actually fewer). It is also used in the hybrid |
@@ -492,21 +730,30 @@ static int mylog2 (unsigned long avalue) | |||
492 | int dbits; | 730 | int dbits; |
493 | 731 | ||
494 | if ((avalue += avalue >> 9) < (1 << 8)) { | 732 | if ((avalue += avalue >> 9) < (1 << 8)) { |
495 | dbits = nbits_table [avalue]; | 733 | dbits = nbits_table [avalue]; |
496 | return (dbits << 8) + log2_table [(avalue << (9 - dbits)) & 0xff]; | 734 | return (dbits << 8) + log2_table [(avalue << (9 - dbits)) & 0xff]; |
497 | } | 735 | } |
498 | else { | 736 | else { |
499 | if (avalue < (1L << 16)) | 737 | if (avalue < (1L << 16)) |
500 | dbits = nbits_table [avalue >> 8] + 8; | 738 | dbits = nbits_table [avalue >> 8] + 8; |
501 | else if (avalue < (1L << 24)) | 739 | else if (avalue < (1L << 24)) |
502 | dbits = nbits_table [avalue >> 16] + 16; | 740 | dbits = nbits_table [avalue >> 16] + 16; |
503 | else | 741 | else |
504 | dbits = nbits_table [avalue >> 24] + 24; | 742 | dbits = nbits_table [avalue >> 24] + 24; |
505 | 743 | ||
506 | return (dbits << 8) + log2_table [(avalue >> (dbits - 9)) & 0xff]; | 744 | return (dbits << 8) + log2_table [(avalue >> (dbits - 9)) & 0xff]; |
507 | } | 745 | } |
508 | } | 746 | } |
509 | 747 | ||
748 | // This function returns the log2 for the specified 32-bit signed value. | ||
749 | // All input values are valid and the return values are in the range of | ||
750 | // +/- 8192. | ||
751 | |||
752 | int log2s (long value) | ||
753 | { | ||
754 | return (value < 0) ? -mylog2 (-value) : mylog2 (value); | ||
755 | } | ||
756 | |||
510 | // This function returns the original integer represented by the supplied | 757 | // This function returns the original integer represented by the supplied |
511 | // logarithm (at least within the provided accuracy). The log is signed, | 758 | // logarithm (at least within the provided accuracy). The log is signed, |
512 | // but since a full 32-bit value is returned this can be used for unsigned | 759 | // but since a full 32-bit value is returned this can be used for unsigned |
@@ -517,26 +764,39 @@ long exp2s (int log) | |||
517 | ulong value; | 764 | ulong value; |
518 | 765 | ||
519 | if (log < 0) | 766 | if (log < 0) |
520 | return -exp2s (-log); | 767 | return -exp2s (-log); |
521 | 768 | ||
522 | value = exp2_table [log & 0xff] | 0x100; | 769 | value = exp2_table [log & 0xff] | 0x100; |
523 | 770 | ||
524 | if ((log >>= 8) <= 9) | 771 | if ((log >>= 8) <= 9) |
525 | return value >> (9 - log); | 772 | return value >> (9 - log); |
526 | else | 773 | else |
527 | return value << (log - 9); | 774 | return value << (log - 9); |
528 | } | 775 | } |
529 | 776 | ||
530 | // These two functions convert internal weights (which are normally +/-1024) | 777 | // These two functions convert internal weights (which are normally +/-1024) |
531 | // to and from an 8-bit signed character version for storage in metadata. The | 778 | // to and from an 8-bit signed character version for storage in metadata. The |
532 | // weights are clipped here in the case that they are outside that range. | 779 | // weights are clipped here in the case that they are outside that range. |
533 | 780 | ||
781 | char store_weight (int weight) | ||
782 | { | ||
783 | if (weight > 1024) | ||
784 | weight = 1024; | ||
785 | else if (weight < -1024) | ||
786 | weight = -1024; | ||
787 | |||
788 | if (weight > 0) | ||
789 | weight -= (weight + 64) >> 7; | ||
790 | |||
791 | return (weight + 4) >> 3; | ||
792 | } | ||
793 | |||
534 | int restore_weight (char weight) | 794 | int restore_weight (char weight) |
535 | { | 795 | { |
536 | int result; | 796 | int result; |
537 | 797 | ||
538 | if ((result = (int) weight << 3) > 0) | 798 | if ((result = (int) weight << 3) > 0) |
539 | result += (result + 64) >> 7; | 799 | result += (result + 64) >> 7; |
540 | 800 | ||
541 | return result; | 801 | return result; |
542 | } | 802 | } |