1 /*
2 Copyright (c) 2012-2021 Genome Research Ltd.
3 Author: James Bonfield <jkb@sanger.ac.uk>
4
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions are met:
7
8 1. Redistributions of source code must retain the above copyright notice,
9 this list of conditions and the following disclaimer.
10
11 2. Redistributions in binary form must reproduce the above copyright notice,
12 this list of conditions and the following disclaimer in the documentation
13 and/or other materials provided with the distribution.
14
15 3. Neither the names Genome Research Ltd and Wellcome Trust Sanger
16 Institute nor the names of its contributors may be used to endorse or promote
17 products derived from this software without specific prior written permission.
18
19 THIS SOFTWARE IS PROVIDED BY GENOME RESEARCH LTD AND CONTRIBUTORS "AS IS" AND
20 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
21 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL GENOME RESEARCH LTD OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31 /*
32 * FIXME: add checking of cram_external_type to return NULL on unsupported
33 * {codec,type} tuples.
34 */
35
36 #define HTS_BUILDING_LIBRARY // Enables HTSLIB_EXPORT, see htslib/hts_defs.h
37 #include <config.h>
38
39 #include <stdlib.h>
40 #include <string.h>
41 #include <assert.h>
42 #include <limits.h>
43 #include <stdint.h>
44 #include <errno.h>
45 #include <stddef.h>
46
47 #include "../htslib/hts_endian.h"
48
49 #if defined(HAVE_EXTERNAL_LIBHTSCODECS)
50 #include <htscodecs/varint.h>
51 #include <htscodecs/pack.h>
52 #include <htscodecs/rle.h>
53 #else
54 #include "../htscodecs/htscodecs/varint.h"
55 #include "../htscodecs/htscodecs/pack.h"
56 #include "../htscodecs/htscodecs/rle.h"
57 #endif
58
59 #include "cram.h"
60
61 /*
62 * ---------------------------------------------------------------------------
63 * Block bit-level I/O functions.
64 * All defined static here to promote easy inlining by the compiler.
65 */
66
67 #if 0
68 /* Get a single bit, MSB first */
69 static signed int get_bit_MSB(cram_block *block) {
70 unsigned int val;
71
72 if (block->byte > block->alloc)
73 return -1;
74
75 val = block->data[block->byte] >> block->bit;
76 if (--block->bit == -1) {
77 block->bit = 7;
78 block->byte++;
79 //printf("(%02X)", block->data[block->byte]);
80 }
81
82 //printf("-B%d-", val&1);
83
84 return val & 1;
85 }
86 #endif
87
88 /*
89 * Count number of successive 0 and 1 bits
90 */
get_one_bits_MSB(cram_block * block)91 static int get_one_bits_MSB(cram_block *block) {
92 int n = 0, b;
93 if (block->byte >= block->uncomp_size)
94 return -1;
95 do {
96 b = block->data[block->byte] >> block->bit;
97 if (--block->bit == -1) {
98 block->bit = 7;
99 block->byte++;
100 if (block->byte == block->uncomp_size && (b&1))
101 return -1;
102 }
103 n++;
104 } while (b&1);
105
106 return n-1;
107 }
108
get_zero_bits_MSB(cram_block * block)109 static int get_zero_bits_MSB(cram_block *block) {
110 int n = 0, b;
111 if (block->byte >= block->uncomp_size)
112 return -1;
113 do {
114 b = block->data[block->byte] >> block->bit;
115 if (--block->bit == -1) {
116 block->bit = 7;
117 block->byte++;
118 if (block->byte == block->uncomp_size && !(b&1))
119 return -1;
120 }
121 n++;
122 } while (!(b&1));
123
124 return n-1;
125 }
126
127 #if 0
128 /* Stores a single bit */
129 static void store_bit_MSB(cram_block *block, unsigned int bit) {
130 if (block->byte >= block->alloc) {
131 block->alloc = block->alloc ? block->alloc*2 : 1024;
132 block->data = realloc(block->data, block->alloc);
133 }
134
135 if (bit)
136 block->data[block->byte] |= (1 << block->bit);
137
138 if (--block->bit == -1) {
139 block->bit = 7;
140 block->byte++;
141 block->data[block->byte] = 0;
142 }
143 }
144 #endif
145
146 #if 0
147 /* Rounds to the next whole byte boundary first */
148 static void store_bytes_MSB(cram_block *block, char *bytes, int len) {
149 if (block->bit != 7) {
150 block->bit = 7;
151 block->byte++;
152 }
153
154 while (block->byte + len >= block->alloc) {
155 block->alloc = block->alloc ? block->alloc*2 : 1024;
156 block->data = realloc(block->data, block->alloc);
157 }
158
159 memcpy(&block->data[block->byte], bytes, len);
160 block->byte += len;
161 }
162 #endif
163
164 /* Local optimised copy for inlining */
get_bits_MSB(cram_block * block,int nbits)165 static inline int64_t get_bits_MSB(cram_block *block, int nbits) {
166 uint64_t val = 0;
167 int i;
168
169 #if 0
170 // Fits within the current byte */
171 if (nbits <= block->bit+1) {
172 val = (block->data[block->byte]>>(block->bit-(nbits-1))) & ((1<<nbits)-1);
173 if ((block->bit -= nbits) == -1) {
174 block->bit = 7;
175 block->byte++;
176 }
177 return val;
178 }
179
180 // partial first byte
181 val = block->data[block->byte] & ((1<<(block->bit+1))-1);
182 nbits -= block->bit+1;
183 block->bit = 7;
184 block->byte++;
185
186 // whole middle bytes
187 while (nbits >= 8) {
188 val = (val << 8) | block->data[block->byte++];
189 nbits -= 8;
190 }
191
192 val <<= nbits;
193 val |= (block->data[block->byte]>>(block->bit-(nbits-1))) & ((1<<nbits)-1);
194 block->bit -= nbits;
195 return val;
196 #endif
197
198 #if 0
199 /* Inefficient implementation! */
200 //printf("{");
201 for (i = 0; i < nbits; i++)
202 //val = (val << 1) | get_bit_MSB(block);
203 GET_BIT_MSB(block, val);
204 #endif
205
206 #if 1
207 /* Combination of 1st two methods */
208 if (nbits <= block->bit+1) {
209 val = (block->data[block->byte]>>(block->bit-(nbits-1))) & ((1<<nbits)-1);
210 if ((block->bit -= nbits) == -1) {
211 block->bit = 7;
212 block->byte++;
213 }
214 return val;
215 }
216
217 switch(nbits) {
218 // case 15: GET_BIT_MSB(block, val); // fall through
219 // case 14: GET_BIT_MSB(block, val); // fall through
220 // case 13: GET_BIT_MSB(block, val); // fall through
221 // case 12: GET_BIT_MSB(block, val); // fall through
222 // case 11: GET_BIT_MSB(block, val); // fall through
223 // case 10: GET_BIT_MSB(block, val); // fall through
224 // case 9: GET_BIT_MSB(block, val); // fall through
225 case 8: GET_BIT_MSB(block, val); // fall through
226 case 7: GET_BIT_MSB(block, val); // fall through
227 case 6: GET_BIT_MSB(block, val); // fall through
228 case 5: GET_BIT_MSB(block, val); // fall through
229 case 4: GET_BIT_MSB(block, val); // fall through
230 case 3: GET_BIT_MSB(block, val); // fall through
231 case 2: GET_BIT_MSB(block, val); // fall through
232 case 1: GET_BIT_MSB(block, val);
233 break;
234
235 default:
236 for (i = 0; i < nbits; i++)
237 //val = (val << 1) | get_bit_MSB(block);
238 GET_BIT_MSB(block, val);
239 }
240 #endif
241
242 //printf("=0x%x}", val);
243
244 return val;
245 }
246
247 /*
248 * Can store up to 24-bits worth of data encoded in an integer value
249 * Possibly we'd want to have a less optimal store_bits function when dealing
250 * with nbits > 24, but for now we assume the codes generated are never
251 * that big. (Given this is only possible with 121392 or more
252 * characters with exactly the correct frequency distribution we check
253 * for it elsewhere.)
254 */
store_bits_MSB(cram_block * block,uint64_t val,int nbits)255 static int store_bits_MSB(cram_block *block, uint64_t val, int nbits) {
256 //fprintf(stderr, " store_bits: %02x %d\n", val, nbits);
257
258 /*
259 * Use slow mode until we tweak the huffman generator to never generate
260 * codes longer than 24-bits.
261 */
262 unsigned int mask;
263
264 if (block->byte+8 >= block->alloc) {
265 if (block->byte) {
266 block->alloc *= 2;
267 block->data = realloc(block->data, block->alloc + 8);
268 if (!block->data)
269 return -1;
270 } else {
271 block->alloc = 1024;
272 block->data = realloc(block->data, block->alloc + 8);
273 if (!block->data)
274 return -1;
275 block->data[0] = 0; // initialise first byte of buffer
276 }
277 }
278
279 /* fits in current bit-field */
280 if (nbits <= block->bit+1) {
281 block->data[block->byte] |= (val << (block->bit+1-nbits));
282 if ((block->bit-=nbits) == -1) {
283 block->bit = 7;
284 block->byte++;
285 block->data[block->byte] = 0;
286 }
287 return 0;
288 }
289
290 block->data[block->byte] |= (val >> (nbits -= block->bit+1));
291 block->bit = 7;
292 block->byte++;
293 block->data[block->byte] = 0;
294
295 mask = 1<<(nbits-1);
296 do {
297 if (val & mask)
298 block->data[block->byte] |= (1 << block->bit);
299 if (--block->bit == -1) {
300 block->bit = 7;
301 block->byte++;
302 block->data[block->byte] = 0;
303 }
304 mask >>= 1;
305 } while(--nbits);
306
307 return 0;
308 }
309
310 /*
311 * Returns the next 'size' bytes from a block, or NULL if insufficient
312 * data left.This is just a pointer into the block data and not an
313 * allocated object, so do not free the result.
314 */
cram_extract_block(cram_block * b,int size)315 static char *cram_extract_block(cram_block *b, int size) {
316 char *cp = (char *)b->data + b->idx;
317 b->idx += size;
318 if (b->idx > b->uncomp_size)
319 return NULL;
320
321 return cp;
322 }
323
324 /*
325 * ---------------------------------------------------------------------------
326 * EXTERNAL
327 *
328 * In CRAM 3.0 and earlier, E_EXTERNAL use the data type to determine the
329 * size of the object being returned. This type is hard coded in the
330 * spec document (changing from uint32 to uint64 requires a spec change)
331 * and there is no data format introspection so implementations have
332 * to determine which size to use based on version numbers. It also
333 * doesn't support signed data.
334 *
335 * With CRAM 4.0 onwards the size and sign of the data is no longer stated
336 * explicitly in the specification. Instead EXTERNAL is replaced by three
337 * new encodings, for bytes and signed / unsigned integers which used a
338 * variable sized encoding.
339 *
340 * For simplicity we use the same encode and decode functions for
341 * bytes (CRAM4) and external (CRAM3). Given we already had code to
342 * replace codec + type into a function pointer it makes little
343 * difference how we ended up at that function. However we disallow
344 * this codec to operate on integer data for CRAM4 onwards.
345 */
cram_external_decode_int(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)346 int cram_external_decode_int(cram_slice *slice, cram_codec *c,
347 cram_block *in, char *out, int *out_size) {
348 char *cp;
349 cram_block *b;
350
351 /* Find the external block */
352 b = cram_get_block_by_id(slice, c->u.external.content_id);
353 if (!b)
354 return *out_size?-1:0;
355
356 cp = (char *)b->data + b->idx;
357 // E_INT and E_LONG are guaranteed single item queries
358 int err = 0;
359 *(int32_t *)out = c->vv->varint_get32(&cp, (char *)b->data + b->uncomp_size, &err);
360 b->idx = cp - (char *)b->data;
361 *out_size = 1;
362
363 return err ? -1 : 0;
364 }
365
cram_external_decode_long(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)366 int cram_external_decode_long(cram_slice *slice, cram_codec *c,
367 cram_block *in, char *out, int *out_size) {
368 char *cp;
369 cram_block *b;
370
371 /* Find the external block */
372 b = cram_get_block_by_id(slice, c->u.external.content_id);
373 if (!b)
374 return *out_size?-1:0;
375
376 cp = (char *)b->data + b->idx;
377 // E_INT and E_LONG are guaranteed single item queries
378 int err = 0;
379 *(int64_t *)out = c->vv->varint_get64(&cp, (char *)b->data + b->uncomp_size, &err);
380 b->idx = cp - (char *)b->data;
381 *out_size = 1;
382
383 return err ? -1 : 0;
384 }
385
cram_external_decode_char(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)386 int cram_external_decode_char(cram_slice *slice, cram_codec *c,
387 cram_block *in, char *out,
388 int *out_size) {
389 char *cp;
390 cram_block *b;
391
392 /* Find the external block */
393 b = cram_get_block_by_id(slice, c->u.external.content_id);
394 if (!b)
395 return *out_size?-1:0;
396
397 cp = cram_extract_block(b, *out_size);
398 if (!cp)
399 return -1;
400
401 if (out)
402 memcpy(out, cp, *out_size);
403 return 0;
404 }
405
cram_external_decode_block(cram_slice * slice,cram_codec * c,cram_block * in,char * out_,int * out_size)406 static int cram_external_decode_block(cram_slice *slice, cram_codec *c,
407 cram_block *in, char *out_,
408 int *out_size) {
409 char *cp;
410 cram_block *out = (cram_block *)out_;
411 cram_block *b = NULL;
412
413 /* Find the external block */
414 b = cram_get_block_by_id(slice, c->u.external.content_id);
415 if (!b)
416 return *out_size?-1:0;
417
418 cp = cram_extract_block(b, *out_size);
419 if (!cp)
420 return -1;
421
422 BLOCK_APPEND(out, cp, *out_size);
423 return 0;
424
425 block_err:
426 return -1;
427 }
428
cram_external_decode_free(cram_codec * c)429 void cram_external_decode_free(cram_codec *c) {
430 if (c)
431 free(c);
432 }
433
434
cram_external_decode_size(cram_slice * slice,cram_codec * c)435 int cram_external_decode_size(cram_slice *slice, cram_codec *c) {
436 cram_block *b;
437
438 /* Find the external block */
439 b = cram_get_block_by_id(slice, c->u.external.content_id);
440 if (!b)
441 return -1;
442
443 return b->uncomp_size;
444 }
445
cram_external_get_block(cram_slice * slice,cram_codec * c)446 cram_block *cram_external_get_block(cram_slice *slice, cram_codec *c) {
447 return cram_get_block_by_id(slice, c->u.external.content_id);
448 }
449
cram_external_decode_init(cram_block_compression_hdr * hdr,char * data,int size,enum cram_encoding codec,enum cram_external_type option,int version,varint_vec * vv)450 cram_codec *cram_external_decode_init(cram_block_compression_hdr *hdr,
451 char *data, int size,
452 enum cram_encoding codec,
453 enum cram_external_type option,
454 int version, varint_vec *vv) {
455 cram_codec *c = NULL;
456 char *cp = data;
457
458 if (size < 1)
459 goto malformed;
460
461 if (!(c = malloc(sizeof(*c))))
462 return NULL;
463
464 c->codec = E_EXTERNAL;
465 if (CRAM_MAJOR_VERS(version) >= 4) {
466 // Version 4 does not permit integer data to be encoded as a
467 // series of bytes. This is used purely for bytes, either
468 // singular or declared as arrays
469 switch (codec) {
470 case E_EXTERNAL:
471 if (option == E_BYTE_ARRAY_BLOCK)
472 c->decode = cram_external_decode_block;
473 else if (option == E_BYTE || option == E_BYTE_ARRAY)
474 c->decode = cram_external_decode_char;
475 else
476 return NULL;
477 break;
478 default:
479 return NULL;
480 }
481 } else {
482 // CRAM 3 and earlier encodes integers as EXTERNAL. We need
483 // use the option field to indicate the input data format so
484 // we know which serialisation format to use.
485 if (option == E_INT)
486 c->decode = cram_external_decode_int;
487 else if (option == E_LONG)
488 c->decode = cram_external_decode_long;
489 else if (option == E_BYTE_ARRAY || option == E_BYTE)
490 c->decode = cram_external_decode_char;
491 else
492 c->decode = cram_external_decode_block;
493 }
494 c->free = cram_external_decode_free;
495 c->size = cram_external_decode_size;
496 c->get_block = cram_external_get_block;
497
498 c->u.external.content_id = vv->varint_get32(&cp, data+size, NULL);
499
500 if (cp - data != size)
501 goto malformed;
502
503 c->u.external.type = option;
504
505 return c;
506
507 malformed:
508 hts_log_error("Malformed external header stream");
509 free(c);
510 return NULL;
511 }
512
cram_external_encode_int(cram_slice * slice,cram_codec * c,char * in,int in_size)513 int cram_external_encode_int(cram_slice *slice, cram_codec *c,
514 char *in, int in_size) {
515 uint32_t *i32 = (uint32_t *)in;
516 return c->vv->varint_put32_blk(c->out, *i32) >= 0 ? 0 : -1;
517 }
518
cram_external_encode_sint(cram_slice * slice,cram_codec * c,char * in,int in_size)519 int cram_external_encode_sint(cram_slice *slice, cram_codec *c,
520 char *in, int in_size) {
521 int32_t *i32 = (int32_t *)in;
522 return c->vv->varint_put32s_blk(c->out, *i32) >= 0 ? 0 : -1;
523 }
524
cram_external_encode_long(cram_slice * slice,cram_codec * c,char * in,int in_size)525 int cram_external_encode_long(cram_slice *slice, cram_codec *c,
526 char *in, int in_size) {
527 uint64_t *i64 = (uint64_t *)in;
528 return c->vv->varint_put64_blk(c->out, *i64) >= 0 ? 0 : -1;
529 }
530
cram_external_encode_slong(cram_slice * slice,cram_codec * c,char * in,int in_size)531 int cram_external_encode_slong(cram_slice *slice, cram_codec *c,
532 char *in, int in_size) {
533 int64_t *i64 = (int64_t *)in;
534 return c->vv->varint_put64s_blk(c->out, *i64) >= 0 ? 0 : -1;
535 }
536
cram_external_encode_char(cram_slice * slice,cram_codec * c,char * in,int in_size)537 int cram_external_encode_char(cram_slice *slice, cram_codec *c,
538 char *in, int in_size) {
539 BLOCK_APPEND(c->out, in, in_size);
540 return 0;
541
542 block_err:
543 return -1;
544 }
545
cram_external_encode_free(cram_codec * c)546 void cram_external_encode_free(cram_codec *c) {
547 if (!c)
548 return;
549 free(c);
550 }
551
cram_external_encode_store(cram_codec * c,cram_block * b,char * prefix,int version)552 int cram_external_encode_store(cram_codec *c, cram_block *b, char *prefix,
553 int version) {
554 char tmp[99], *tp = tmp, *tpend = tmp+99;
555 int len = 0, r = 0, n;
556
557 if (prefix) {
558 size_t l = strlen(prefix);
559 BLOCK_APPEND(b, prefix, l);
560 len += l;
561 }
562
563 tp += c->vv->varint_put32(tp, tpend, c->u.e_external.content_id);
564 len += (n = c->vv->varint_put32_blk(b, c->codec)); r |= n;
565 len += (n = c->vv->varint_put32_blk(b, tp-tmp)); r |= n;
566 BLOCK_APPEND(b, tmp, tp-tmp);
567 len += tp-tmp;
568
569 if (r > 0)
570 return len;
571
572 block_err:
573 return -1;
574 }
575
cram_external_encode_init(cram_stats * st,enum cram_encoding codec,enum cram_external_type option,void * dat,int version,varint_vec * vv)576 cram_codec *cram_external_encode_init(cram_stats *st,
577 enum cram_encoding codec,
578 enum cram_external_type option,
579 void *dat,
580 int version, varint_vec *vv) {
581 cram_codec *c;
582
583 c = malloc(sizeof(*c));
584 if (!c)
585 return NULL;
586 c->codec = E_EXTERNAL;
587 c->free = cram_external_encode_free;
588 if (CRAM_MAJOR_VERS(version) >= 4) {
589 // Version 4 does not permit integer data to be encoded as a
590 // series of bytes. This is used purely for bytes, either
591 // singular or declared as arrays
592 switch (codec) {
593 case E_EXTERNAL:
594 if (option != E_BYTE && option != E_BYTE_ARRAY)
595 return NULL;
596 c->encode = cram_external_encode_char;
597 break;
598 default:
599 return NULL;
600 }
601 } else {
602 // CRAM 3 and earlier encodes integers as EXTERNAL. We need
603 // use the option field to indicate the input data format so
604 // we know which serialisation format to use.
605 if (option == E_INT)
606 c->encode = cram_external_encode_int;
607 else if (option == E_LONG)
608 c->encode = cram_external_encode_long;
609 else if (option == E_BYTE_ARRAY || option == E_BYTE)
610 c->encode = cram_external_encode_char;
611 else
612 abort();
613 }
614 c->store = cram_external_encode_store;
615 c->flush = NULL;
616
617 c->u.e_external.content_id = (size_t)dat;
618
619 return c;
620 }
621
622 /*
623 * ---------------------------------------------------------------------------
624 * VARINT
625 *
626 * In CRAM 3.0 and earlier, E_EXTERNAL stored both integers in ITF8
627 * format as well as bytes. In CRAM 4 EXTERNAL is only for bytes and
628 * byte arrays, with two dedicated encodings for integers:
629 * VARINT_SIGNED and VARINT_UNSIGNED. These also differ a little to
630 * EXTERNAL with the addition of an offset field, meaning we can store
631 * values in, say, the range -2 to 1 million without needing to use
632 * a signed zig-zag transformation.
633 */
cram_varint_decode_int(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)634 int cram_varint_decode_int(cram_slice *slice, cram_codec *c,
635 cram_block *in, char *out, int *out_size) {
636 char *cp;
637 cram_block *b;
638
639 /* Find the data block */
640 b = cram_get_block_by_id(slice, c->u.varint.content_id);
641 if (!b)
642 return *out_size?-1:0;
643
644 cp = (char *)b->data + b->idx;
645 // E_INT and E_LONG are guaranteed single item queries
646 int err = 0;
647 *(int32_t *)out = c->vv->varint_get32(&cp,
648 (char *)b->data + b->uncomp_size,
649 &err) + c->u.varint.offset;
650 b->idx = cp - (char *)b->data;
651 *out_size = 1;
652
653 return err ? -1 : 0;
654 }
655
cram_varint_decode_sint(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)656 int cram_varint_decode_sint(cram_slice *slice, cram_codec *c,
657 cram_block *in, char *out, int *out_size) {
658 char *cp;
659 cram_block *b;
660
661 /* Find the data block */
662 b = cram_get_block_by_id(slice, c->u.varint.content_id);
663 if (!b)
664 return *out_size?-1:0;
665
666 cp = (char *)b->data + b->idx;
667 // E_INT and E_LONG are guaranteed single item queries
668 int err = 0;
669 *(int32_t *)out = c->vv->varint_get32s(&cp,
670 (char *)b->data + b->uncomp_size,
671 &err) + c->u.varint.offset;
672 b->idx = cp - (char *)b->data;
673 *out_size = 1;
674
675 return err ? -1 : 0;
676 }
677
cram_varint_decode_long(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)678 int cram_varint_decode_long(cram_slice *slice, cram_codec *c,
679 cram_block *in, char *out, int *out_size) {
680 char *cp;
681 cram_block *b;
682
683 /* Find the data block */
684 b = cram_get_block_by_id(slice, c->u.varint.content_id);
685 if (!b)
686 return *out_size?-1:0;
687
688 cp = (char *)b->data + b->idx;
689 // E_INT and E_LONG are guaranteed single item queries
690 int err = 0;
691 *(int64_t *)out = c->vv->varint_get64(&cp,
692 (char *)b->data + b->uncomp_size,
693 &err) + c->u.varint.offset;
694 b->idx = cp - (char *)b->data;
695 *out_size = 1;
696
697 return err ? -1 : 0;
698 }
699
cram_varint_decode_slong(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)700 int cram_varint_decode_slong(cram_slice *slice, cram_codec *c,
701 cram_block *in, char *out, int *out_size) {
702 char *cp;
703 cram_block *b;
704
705 /* Find the data block */
706 b = cram_get_block_by_id(slice, c->u.varint.content_id);
707 if (!b)
708 return *out_size?-1:0;
709
710 cp = (char *)b->data + b->idx;
711 // E_INT and E_LONG are guaranteed single item queries
712 int err = 0;
713 *(int64_t *)out = c->vv->varint_get64s(&cp,
714 (char *)b->data + b->uncomp_size,
715 &err) + c->u.varint.offset;
716 b->idx = cp - (char *)b->data;
717 *out_size = 1;
718
719 return err ? -1 : 0;
720 }
721
cram_varint_decode_free(cram_codec * c)722 void cram_varint_decode_free(cram_codec *c) {
723 if (c)
724 free(c);
725 }
726
cram_varint_decode_size(cram_slice * slice,cram_codec * c)727 int cram_varint_decode_size(cram_slice *slice, cram_codec *c) {
728 cram_block *b;
729
730 /* Find the data block */
731 b = cram_get_block_by_id(slice, c->u.varint.content_id);
732 if (!b)
733 return -1;
734
735 return b->uncomp_size;
736 }
737
cram_varint_get_block(cram_slice * slice,cram_codec * c)738 cram_block *cram_varint_get_block(cram_slice *slice, cram_codec *c) {
739 return cram_get_block_by_id(slice, c->u.varint.content_id);
740 }
741
cram_varint_decode_init(cram_block_compression_hdr * hdr,char * data,int size,enum cram_encoding codec,enum cram_external_type option,int version,varint_vec * vv)742 cram_codec *cram_varint_decode_init(cram_block_compression_hdr *hdr,
743 char *data, int size,
744 enum cram_encoding codec,
745 enum cram_external_type option,
746 int version, varint_vec *vv) {
747 cram_codec *c;
748 char *cp = data, *cp_end = data+size;
749
750 if (!(c = malloc(sizeof(*c))))
751 return NULL;
752
753 c->codec = codec;
754
755 // Function pointer choice is theoretically by codec type.
756 // Given we have some vars as int32 and some as int64 we
757 // use option too for sizing, although on disk format
758 // does not change.
759 switch(codec) {
760 case E_VARINT_UNSIGNED:
761 c->decode = (option == E_INT)
762 ? cram_varint_decode_int
763 : cram_varint_decode_long;
764 break;
765 case E_VARINT_SIGNED:
766 c->decode = (option == E_INT)
767 ? cram_varint_decode_sint
768 : cram_varint_decode_slong;
769 break;
770 default:
771 return NULL;
772 }
773
774 c->free = cram_varint_decode_free;
775 c->size = cram_varint_decode_size;
776 c->get_block = cram_varint_get_block;
777
778 c->u.varint.content_id = vv->varint_get32 (&cp, cp_end, NULL);
779 c->u.varint.offset = vv->varint_get64s(&cp, cp_end, NULL);
780
781 if (cp - data != size) {
782 fprintf(stderr, "Malformed varint header stream\n");
783 free(c);
784 return NULL;
785 }
786
787 c->u.varint.type = option;
788
789 return c;
790 }
791
cram_varint_encode_int(cram_slice * slice,cram_codec * c,char * in,int in_size)792 int cram_varint_encode_int(cram_slice *slice, cram_codec *c,
793 char *in, int in_size) {
794 uint32_t *i32 = (uint32_t *)in;
795 return c->vv->varint_put32_blk(c->out, *i32 - c->u.varint.offset) >= 0
796 ? 0 : -1;
797 }
798
cram_varint_encode_sint(cram_slice * slice,cram_codec * c,char * in,int in_size)799 int cram_varint_encode_sint(cram_slice *slice, cram_codec *c,
800 char *in, int in_size) {
801 int32_t *i32 = (int32_t *)in;
802 return c->vv->varint_put32s_blk(c->out, *i32 - c->u.varint.offset) >= 0
803 ? 0 : -1;
804 }
805
cram_varint_encode_long(cram_slice * slice,cram_codec * c,char * in,int in_size)806 int cram_varint_encode_long(cram_slice *slice, cram_codec *c,
807 char *in, int in_size) {
808 uint64_t *i64 = (uint64_t *)in;
809 return c->vv->varint_put64_blk(c->out, *i64 - c->u.varint.offset) >= 0
810 ? 0 : -1;
811 }
812
cram_varint_encode_slong(cram_slice * slice,cram_codec * c,char * in,int in_size)813 int cram_varint_encode_slong(cram_slice *slice, cram_codec *c,
814 char *in, int in_size) {
815 int64_t *i64 = (int64_t *)in;
816 return c->vv->varint_put64s_blk(c->out, *i64 - c->u.varint.offset) >= 0
817 ? 0 : -1;
818 }
819
cram_varint_encode_free(cram_codec * c)820 void cram_varint_encode_free(cram_codec *c) {
821 if (!c)
822 return;
823 free(c);
824 }
825
cram_varint_encode_store(cram_codec * c,cram_block * b,char * prefix,int version)826 int cram_varint_encode_store(cram_codec *c, cram_block *b, char *prefix,
827 int version) {
828 char tmp[99], *tp = tmp;
829 int len = 0;
830
831 if (prefix) {
832 size_t l = strlen(prefix);
833 BLOCK_APPEND(b, prefix, l);
834 len += l;
835 }
836
837 tp += c->vv->varint_put32 (tp, NULL, c->u.e_varint.content_id);
838 tp += c->vv->varint_put64s(tp, NULL, c->u.e_varint.offset);
839 len += c->vv->varint_put32_blk(b, c->codec);
840 len += c->vv->varint_put32_blk(b, tp-tmp);
841 BLOCK_APPEND(b, tmp, tp-tmp);
842 len += tp-tmp;
843
844 return len;
845
846 block_err:
847 return -1;
848 }
849
cram_varint_encode_init(cram_stats * st,enum cram_encoding codec,enum cram_external_type option,void * dat,int version,varint_vec * vv)850 cram_codec *cram_varint_encode_init(cram_stats *st,
851 enum cram_encoding codec,
852 enum cram_external_type option,
853 void *dat,
854 int version, varint_vec *vv) {
855 cram_codec *c;
856
857 if (!(c = malloc(sizeof(*c))))
858 return NULL;
859
860 c->u.e_varint.offset = 0;
861 if (st) {
862 // Marginal difference so far! Not worth the hassle?
863 if (st->min_val < 0 && st->min_val >= -127
864 && st->max_val / -st->min_val > 100) {
865 c->u.e_varint.offset = -st->min_val;
866 codec = E_VARINT_UNSIGNED;
867 } else if (st->min_val > 0) {
868 c->u.e_varint.offset = -st->min_val;
869 }
870 }
871
872 c->codec = codec;
873 c->free = cram_varint_encode_free;
874
875 // Function pointer choice is theoretically by codec type.
876 // Given we have some vars as int32 and some as int64 we
877 // use option too for sizing, although on disk format
878 // does not change.
879 switch (codec) {
880 case E_VARINT_UNSIGNED:
881 c->encode = (option == E_INT)
882 ? cram_varint_encode_int
883 : cram_varint_encode_long;
884 break;
885 case E_VARINT_SIGNED:
886 c->encode = (option == E_INT)
887 ? cram_varint_encode_sint
888 : cram_varint_encode_slong;
889 break;
890 default:
891 return NULL;
892 }
893 c->store = cram_varint_encode_store;
894 c->flush = NULL;
895
896 c->u.e_varint.content_id = (size_t)dat;
897
898 return c;
899 }
900 /*
901 * ---------------------------------------------------------------------------
902 * CONST_BYTE and CONST_INT
903 */
cram_const_decode_byte(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)904 int cram_const_decode_byte(cram_slice *slice, cram_codec *c,
905 cram_block *in, char *out, int *out_size) {
906 int i, n;
907
908 for (i = 0, n = *out_size; i < n; i++)
909 out[i] = c->u.xconst.val;
910
911 return 0;
912 }
913
cram_const_decode_int(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)914 int cram_const_decode_int(cram_slice *slice, cram_codec *c,
915 cram_block *in, char *out, int *out_size) {
916 int32_t *out_i = (int32_t *)out;
917 int i, n;
918
919 for (i = 0, n = *out_size; i < n; i++)
920 out_i[i] = c->u.xconst.val;
921
922 return 0;
923 }
924
cram_const_decode_long(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)925 int cram_const_decode_long(cram_slice *slice, cram_codec *c,
926 cram_block *in, char *out, int *out_size) {
927 int64_t *out_i = (int64_t *)out;
928 int i, n;
929
930 for (i = 0, n = *out_size; i < n; i++)
931 out_i[i] = c->u.xconst.val;
932
933 return 0;
934 }
935
cram_const_decode_free(cram_codec * c)936 void cram_const_decode_free(cram_codec *c) {
937 if (c)
938 free(c);
939 }
940
cram_const_decode_size(cram_slice * slice,cram_codec * c)941 int cram_const_decode_size(cram_slice *slice, cram_codec *c) {
942 return 0;
943 }
944
cram_const_decode_init(cram_block_compression_hdr * hdr,char * data,int size,enum cram_encoding codec,enum cram_external_type option,int version,varint_vec * vv)945 cram_codec *cram_const_decode_init(cram_block_compression_hdr *hdr,
946 char *data, int size,
947 enum cram_encoding codec,
948 enum cram_external_type option,
949 int version, varint_vec *vv) {
950 cram_codec *c;
951 char *cp = data;
952
953 if (!(c = malloc(sizeof(*c))))
954 return NULL;
955
956 c->codec = codec;
957 if (codec == E_CONST_BYTE)
958 c->decode = cram_const_decode_byte;
959 else if (option == E_INT)
960 c->decode = cram_const_decode_int;
961 else
962 c->decode = cram_const_decode_long;
963 c->free = cram_const_decode_free;
964 c->size = cram_const_decode_size;
965 c->get_block = NULL;
966
967 c->u.xconst.val = vv->varint_get64s(&cp, data+size, NULL);
968
969 if (cp - data != size) {
970 fprintf(stderr, "Malformed const header stream\n");
971 free(c);
972 return NULL;
973 }
974
975 return c;
976 }
977
cram_const_encode(cram_slice * slice,cram_codec * c,char * in,int in_size)978 int cram_const_encode(cram_slice *slice, cram_codec *c,
979 char *in, int in_size) {
980 return 0;
981 }
982
cram_const_encode_store(cram_codec * c,cram_block * b,char * prefix,int version)983 int cram_const_encode_store(cram_codec *c, cram_block *b, char *prefix,
984 int version) {
985 char tmp[99], *tp = tmp;
986 int len = 0;
987
988 if (prefix) {
989 size_t l = strlen(prefix);
990 BLOCK_APPEND(b, prefix, l);
991 len += l;
992 }
993
994 tp += c->vv->varint_put64s(tp, NULL, c->u.xconst.val);
995 len += c->vv->varint_put32_blk(b, c->codec);
996 len += c->vv->varint_put32_blk(b, tp-tmp);
997 BLOCK_APPEND(b, tmp, tp-tmp);
998 len += tp-tmp;
999
1000 return len;
1001
1002 block_err:
1003 return -1;
1004 }
1005
cram_const_encode_init(cram_stats * st,enum cram_encoding codec,enum cram_external_type option,void * dat,int version,varint_vec * vv)1006 cram_codec *cram_const_encode_init(cram_stats *st,
1007 enum cram_encoding codec,
1008 enum cram_external_type option,
1009 void *dat,
1010 int version, varint_vec *vv) {
1011 cram_codec *c;
1012
1013 if (!(c = malloc(sizeof(*c))))
1014 return NULL;
1015
1016 c->codec = codec;
1017 c->free = cram_const_decode_free; // as as decode
1018 c->encode = cram_const_encode; // a nop
1019 c->store = cram_const_encode_store;
1020 c->flush = NULL;
1021 c->u.e_xconst.val = st->min_val;
1022
1023 return c;
1024 }
1025
1026 /*
1027 * ---------------------------------------------------------------------------
1028 * BETA
1029 */
cram_beta_decode_long(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)1030 int cram_beta_decode_long(cram_slice *slice, cram_codec *c, cram_block *in, char *out, int *out_size) {
1031 int64_t *out_i = (int64_t *)out;
1032 int i, n = *out_size;
1033
1034 if (c->u.beta.nbits) {
1035 if (cram_not_enough_bits(in, c->u.beta.nbits * n))
1036 return -1;
1037
1038 for (i = 0; i < n; i++)
1039 out_i[i] = get_bits_MSB(in, c->u.beta.nbits) - c->u.beta.offset;
1040 } else {
1041 for (i = 0; i < n; i++)
1042 out_i[i] = -c->u.beta.offset;
1043 }
1044
1045 return 0;
1046 }
1047
cram_beta_decode_int(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)1048 int cram_beta_decode_int(cram_slice *slice, cram_codec *c, cram_block *in, char *out, int *out_size) {
1049 int32_t *out_i = (int32_t *)out;
1050 int i, n = *out_size;
1051
1052 if (c->u.beta.nbits) {
1053 if (cram_not_enough_bits(in, c->u.beta.nbits * n))
1054 return -1;
1055
1056 for (i = 0; i < n; i++)
1057 out_i[i] = get_bits_MSB(in, c->u.beta.nbits) - c->u.beta.offset;
1058 } else {
1059 for (i = 0; i < n; i++)
1060 out_i[i] = -c->u.beta.offset;
1061 }
1062
1063 return 0;
1064 }
1065
cram_beta_decode_char(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)1066 int cram_beta_decode_char(cram_slice *slice, cram_codec *c, cram_block *in, char *out, int *out_size) {
1067 int i, n = *out_size;
1068
1069
1070 if (c->u.beta.nbits) {
1071 if (cram_not_enough_bits(in, c->u.beta.nbits * n))
1072 return -1;
1073
1074 if (out)
1075 for (i = 0; i < n; i++)
1076 out[i] = get_bits_MSB(in, c->u.beta.nbits) - c->u.beta.offset;
1077 else
1078 for (i = 0; i < n; i++)
1079 get_bits_MSB(in, c->u.beta.nbits);
1080 } else {
1081 if (out)
1082 for (i = 0; i < n; i++)
1083 out[i] = -c->u.beta.offset;
1084 }
1085
1086 return 0;
1087 }
1088
cram_beta_decode_free(cram_codec * c)1089 void cram_beta_decode_free(cram_codec *c) {
1090 if (c)
1091 free(c);
1092 }
1093
cram_beta_decode_init(cram_block_compression_hdr * hdr,char * data,int size,enum cram_encoding codec,enum cram_external_type option,int version,varint_vec * vv)1094 cram_codec *cram_beta_decode_init(cram_block_compression_hdr *hdr,
1095 char *data, int size,
1096 enum cram_encoding codec,
1097 enum cram_external_type option,
1098 int version, varint_vec *vv) {
1099 cram_codec *c;
1100 char *cp = data;
1101
1102 if (!(c = malloc(sizeof(*c))))
1103 return NULL;
1104
1105 c->codec = E_BETA;
1106 if (option == E_INT || option == E_SINT)
1107 c->decode = cram_beta_decode_int;
1108 else if (option == E_LONG || option == E_SLONG)
1109 c->decode = cram_beta_decode_long;
1110 else if (option == E_BYTE_ARRAY || option == E_BYTE)
1111 c->decode = cram_beta_decode_char;
1112 else {
1113 hts_log_error("BYTE_ARRAYs not supported by this codec");
1114 free(c);
1115 return NULL;
1116 }
1117 c->free = cram_beta_decode_free;
1118
1119 c->u.beta.nbits = -1;
1120 c->u.beta.offset = vv->varint_get32(&cp, data + size, NULL);
1121 if (cp < data + size) // Ensure test below works
1122 c->u.beta.nbits = vv->varint_get32(&cp, data + size, NULL);
1123
1124 if (cp - data != size
1125 || c->u.beta.nbits < 0 || c->u.beta.nbits > 8 * sizeof(int)) {
1126 hts_log_error("Malformed beta header stream");
1127 free(c);
1128 return NULL;
1129 }
1130
1131 return c;
1132 }
1133
cram_beta_encode_store(cram_codec * c,cram_block * b,char * prefix,int version)1134 int cram_beta_encode_store(cram_codec *c, cram_block *b,
1135 char *prefix, int version) {
1136 int len = 0, r = 0, n;
1137
1138 if (prefix) {
1139 size_t l = strlen(prefix);
1140 BLOCK_APPEND(b, prefix, l);
1141 len += l;
1142 }
1143
1144 len += (n = c->vv->varint_put32_blk(b, c->codec)); r |= n;
1145 // codec length
1146 len += (n = c->vv->varint_put32_blk(b, c->vv->varint_size(c->u.e_beta.offset)
1147 + c->vv->varint_size(c->u.e_beta.nbits)));
1148 r |= n;
1149 len += (n = c->vv->varint_put32_blk(b, c->u.e_beta.offset)); r |= n;
1150 len += (n = c->vv->varint_put32_blk(b, c->u.e_beta.nbits)); r |= n;
1151
1152 if (r > 0) return len;
1153
1154 block_err:
1155 return -1;
1156 }
1157
cram_beta_encode_long(cram_slice * slice,cram_codec * c,char * in,int in_size)1158 int cram_beta_encode_long(cram_slice *slice, cram_codec *c,
1159 char *in, int in_size) {
1160 int64_t *syms = (int64_t *)in;
1161 int i, r = 0;
1162
1163 for (i = 0; i < in_size; i++)
1164 r |= store_bits_MSB(c->out, syms[i] + c->u.e_beta.offset,
1165 c->u.e_beta.nbits);
1166
1167 return r;
1168 }
1169
cram_beta_encode_int(cram_slice * slice,cram_codec * c,char * in,int in_size)1170 int cram_beta_encode_int(cram_slice *slice, cram_codec *c,
1171 char *in, int in_size) {
1172 int *syms = (int *)in;
1173 int i, r = 0;
1174
1175 for (i = 0; i < in_size; i++)
1176 r |= store_bits_MSB(c->out, syms[i] + c->u.e_beta.offset,
1177 c->u.e_beta.nbits);
1178
1179 return r;
1180 }
1181
cram_beta_encode_char(cram_slice * slice,cram_codec * c,char * in,int in_size)1182 int cram_beta_encode_char(cram_slice *slice, cram_codec *c,
1183 char *in, int in_size) {
1184 unsigned char *syms = (unsigned char *)in;
1185 int i, r = 0;
1186
1187 for (i = 0; i < in_size; i++)
1188 r |= store_bits_MSB(c->out, syms[i] + c->u.e_beta.offset,
1189 c->u.e_beta.nbits);
1190
1191 return r;
1192 }
1193
cram_beta_encode_free(cram_codec * c)1194 void cram_beta_encode_free(cram_codec *c) {
1195 if (c) free(c);
1196 }
1197
cram_beta_encode_init(cram_stats * st,enum cram_encoding codec,enum cram_external_type option,void * dat,int version,varint_vec * vv)1198 cram_codec *cram_beta_encode_init(cram_stats *st,
1199 enum cram_encoding codec,
1200 enum cram_external_type option,
1201 void *dat,
1202 int version, varint_vec *vv) {
1203 cram_codec *c;
1204 int min_val, max_val, len = 0;
1205 int64_t range;
1206
1207 c = malloc(sizeof(*c));
1208 if (!c)
1209 return NULL;
1210 c->codec = E_BETA;
1211 c->free = cram_beta_encode_free;
1212 if (option == E_INT || option == E_SINT)
1213 c->encode = cram_beta_encode_int;
1214 else if (option == E_LONG || option == E_SLONG)
1215 c->encode = cram_beta_encode_long;
1216 else
1217 c->encode = cram_beta_encode_char;
1218 c->store = cram_beta_encode_store;
1219 c->flush = NULL;
1220
1221 if (dat) {
1222 min_val = ((int *)dat)[0];
1223 max_val = ((int *)dat)[1];
1224 } else {
1225 min_val = INT_MAX;
1226 max_val = INT_MIN;
1227 int i;
1228 for (i = 0; i < MAX_STAT_VAL; i++) {
1229 if (!st->freqs[i])
1230 continue;
1231 if (min_val > i)
1232 min_val = i;
1233 max_val = i;
1234 }
1235 if (st->h) {
1236 khint_t k;
1237
1238 for (k = kh_begin(st->h); k != kh_end(st->h); k++) {
1239 if (!kh_exist(st->h, k))
1240 continue;
1241
1242 i = kh_key(st->h, k);
1243 if (min_val > i)
1244 min_val = i;
1245 if (max_val < i)
1246 max_val = i;
1247 }
1248 }
1249 }
1250
1251 assert(max_val >= min_val);
1252 c->u.e_beta.offset = -min_val;
1253 range = (int64_t) max_val - min_val;
1254 while (range) {
1255 len++;
1256 range >>= 1;
1257 }
1258 c->u.e_beta.nbits = len;
1259
1260 return c;
1261 }
1262
1263 /*
1264 * ---------------------------------------------------------------------------
1265 * XPACK: Packing multiple values into a single byte. A fast transform that
1266 * reduces time taken by entropy encoder and may also improve compression.
1267 *
1268 * This also has the additional requirement that the data series is not
1269 * interleaved with another, permitting efficient encoding and decoding
1270 * of all elements enmasse instead of needing to only extract the bits
1271 * necessary per item.
1272 */
cram_xpack_decode_long(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)1273 int cram_xpack_decode_long(cram_slice *slice, cram_codec *c, cram_block *in, char *out, int *out_size) {
1274 int64_t *out_i = (int64_t *)out;
1275 int i, n = *out_size;
1276
1277 if (c->u.xpack.nbits) {
1278 for (i = 0; i < n; i++)
1279 out_i[i] = c->u.xpack.rmap[get_bits_MSB(in, c->u.xpack.nbits)];
1280 } else {
1281 for (i = 0; i < n; i++)
1282 out_i[i] = c->u.xpack.rmap[0];
1283 }
1284
1285 return 0;
1286 }
1287
cram_xpack_decode_int(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)1288 int cram_xpack_decode_int(cram_slice *slice, cram_codec *c, cram_block *in, char *out, int *out_size) {
1289 int32_t *out_i = (int32_t *)out;
1290 int i, n = *out_size;
1291
1292 if (c->u.xpack.nbits) {
1293 if (cram_not_enough_bits(in, c->u.xpack.nbits * n))
1294 return -1;
1295
1296 for (i = 0; i < n; i++)
1297 out_i[i] = c->u.xpack.rmap[get_bits_MSB(in, c->u.xpack.nbits)];
1298 } else {
1299 for (i = 0; i < n; i++)
1300 out_i[i] = c->u.xpack.rmap[0];
1301 }
1302
1303 return 0;
1304 }
1305
cram_xpack_decode_expand_char(cram_slice * slice,cram_codec * c)1306 static int cram_xpack_decode_expand_char(cram_slice *slice, cram_codec *c) {
1307 cram_block *b = slice->block_by_id[512 + c->codec_id];
1308 if (b)
1309 return 0;
1310
1311 // get sub-codec data.
1312 cram_block *sub_b = c->u.xpack.sub_codec->get_block(slice, c->u.xpack.sub_codec);
1313 if (!sub_b)
1314 return -1;
1315
1316 // Allocate local block to expand into
1317 b = slice->block_by_id[512 + c->codec_id] = cram_new_block(0, 0);
1318 if (!b)
1319 return -1;
1320 int n = sub_b->uncomp_size * 8/c->u.xpack.nbits;
1321 BLOCK_GROW(b, n);
1322 b->uncomp_size = n;
1323
1324 uint8_t p[256];
1325 int z;
1326 for (z = 0; z < 256; z++)
1327 p[z] = c->u.xpack.rmap[z];
1328 hts_unpack(sub_b->data, sub_b->uncomp_size, b->data, b->uncomp_size,
1329 8 / c->u.xpack.nbits, p);
1330
1331 return 0;
1332
1333 block_err:
1334 return -1;
1335 }
1336
cram_xpack_decode_char(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)1337 int cram_xpack_decode_char(cram_slice *slice, cram_codec *c, cram_block *in, char *out, int *out_size) {
1338 // FIXME: we need to ban data-series interleaving in the spec for this to work.
1339
1340 // Remember this may be called when threaded and multi-slice per container.
1341 // Hence one cram_codec instance, multiple slices, multiple blocks.
1342 // We therefore have to cache appropriate block info in slice and not codec.
1343 // b = cram_get_block_by_id(slice, c->external.content_id);
1344 if (c->u.xpack.nval > 1) {
1345 cram_xpack_decode_expand_char(slice, c);
1346 cram_block *b = slice->block_by_id[512 + c->codec_id];
1347 if (!b)
1348 return -1;
1349
1350 if (out)
1351 memcpy(out, b->data + b->byte, *out_size);
1352 b->byte += *out_size;
1353 } else {
1354 memset(out, c->u.xpack.rmap[0], *out_size);
1355 }
1356
1357 return 0;
1358 }
1359
cram_xpack_decode_free(cram_codec * c)1360 void cram_xpack_decode_free(cram_codec *c) {
1361 if (!c) return;
1362
1363 if (c->u.xpack.sub_codec)
1364 c->u.xpack.sub_codec->free(c->u.xpack.sub_codec);
1365
1366 //free(slice->block_by_id[512 + c->codec_id]);
1367 //slice->block_by_id[512 + c->codec_id] = 0;
1368
1369 free(c);
1370 }
1371
cram_xpack_decode_size(cram_slice * slice,cram_codec * c)1372 int cram_xpack_decode_size(cram_slice *slice, cram_codec *c) {
1373 cram_xpack_decode_expand_char(slice, c);
1374 return slice->block_by_id[512 + c->codec_id]->uncomp_size;
1375 }
1376
cram_xpack_get_block(cram_slice * slice,cram_codec * c)1377 cram_block *cram_xpack_get_block(cram_slice *slice, cram_codec *c) {
1378 cram_xpack_decode_expand_char(slice, c);
1379 return slice->block_by_id[512 + c->codec_id];
1380 }
1381
cram_xpack_decode_init(cram_block_compression_hdr * hdr,char * data,int size,enum cram_encoding codec,enum cram_external_type option,int version,varint_vec * vv)1382 cram_codec *cram_xpack_decode_init(cram_block_compression_hdr *hdr,
1383 char *data, int size,
1384 enum cram_encoding codec,
1385 enum cram_external_type option,
1386 int version, varint_vec *vv) {
1387 cram_codec *c;
1388 char *cp = data;
1389 char *endp = data+size;
1390
1391 if (!(c = calloc(1, sizeof(*c))))
1392 return NULL;
1393
1394 c->codec = E_XPACK;
1395 if (option == E_LONG)
1396 c->decode = cram_xpack_decode_long;
1397 else if (option == E_INT)
1398 c->decode = cram_xpack_decode_int;
1399 else if (option == E_BYTE_ARRAY || option == E_BYTE)
1400 c->decode = cram_xpack_decode_char;
1401 else {
1402 fprintf(stderr, "BYTE_ARRAYs not supported by this codec\n");
1403 goto malformed;
1404 }
1405 c->free = cram_xpack_decode_free;
1406 c->size = cram_xpack_decode_size;
1407 c->get_block = cram_xpack_get_block;
1408
1409 c->u.xpack.nbits = vv->varint_get32(&cp, endp, NULL);
1410 c->u.xpack.nval = vv->varint_get32(&cp, endp, NULL);
1411 if (c->u.xpack.nbits >= 8 || c->u.xpack.nbits < 0 ||
1412 c->u.xpack.nval > 256 || c->u.xpack.nval < 0)
1413 goto malformed;
1414 int i;
1415 for (i = 0; i < c->u.xpack.nval; i++) {
1416 uint32_t v = vv->varint_get32(&cp, endp, NULL);
1417 if (v >= 256)
1418 goto malformed;
1419 c->u.xpack.rmap[i] = v; // reverse map: e.g 0-3 to P,A,C,K
1420 }
1421
1422 int encoding = vv->varint_get32(&cp, endp, NULL);
1423 int sub_size = vv->varint_get32(&cp, endp, NULL);
1424 if (sub_size < 0 || endp - cp < sub_size)
1425 goto malformed;
1426 c->u.xpack.sub_codec = cram_decoder_init(hdr, encoding, cp, sub_size,
1427 option, version, vv);
1428 if (c->u.xpack.sub_codec == NULL)
1429 goto malformed;
1430 cp += sub_size;
1431
1432 if (cp - data != size
1433 || c->u.xpack.nbits < 0 || c->u.xpack.nbits > 8 * sizeof(int64_t)) {
1434 malformed:
1435 fprintf(stderr, "Malformed xpack header stream\n");
1436 cram_xpack_decode_free(c);
1437 return NULL;
1438 }
1439
1440 return c;
1441 }
1442
cram_xpack_encode_flush(cram_codec * c)1443 int cram_xpack_encode_flush(cram_codec *c) {
1444 // Pack the buffered up data
1445 int meta_len;
1446 uint64_t out_len;
1447 uint8_t out_meta[1024];
1448 uint8_t *out = hts_pack(BLOCK_DATA(c->out), BLOCK_SIZE(c->out),
1449 out_meta, &meta_len, &out_len);
1450
1451 // We now need to pass this through the next layer of transform
1452 if (c->u.e_xpack.sub_codec->encode(NULL, // also indicates flush incoming
1453 c->u.e_xpack.sub_codec,
1454 (char *)out, out_len))
1455 return -1;
1456
1457 int r = 0;
1458 if (c->u.e_xpack.sub_codec->flush)
1459 r = c->u.e_xpack.sub_codec->flush(c->u.e_xpack.sub_codec);
1460
1461 free(out);
1462 return r;
1463 }
1464
cram_xpack_encode_store(cram_codec * c,cram_block * b,char * prefix,int version)1465 int cram_xpack_encode_store(cram_codec *c, cram_block *b,
1466 char *prefix, int version) {
1467 int len = 0, r = 0, n;
1468
1469 if (prefix) {
1470 size_t l = strlen(prefix);
1471 BLOCK_APPEND(b, prefix, l);
1472 len += l;
1473 }
1474
1475 // Store sub-codec
1476 cram_codec *tc = c->u.e_xpack.sub_codec;
1477 cram_block *tb = cram_new_block(0, 0);
1478 if (!tb)
1479 return -1;
1480 int len2 = tc->store(tc, tb, NULL, version);
1481
1482 len += (n = c->vv->varint_put32_blk(b, c->codec)); r |= n;
1483
1484 // codec length
1485 int len1 = 0, i;
1486 for (i = 0; i < c->u.e_xpack.nval; i++)
1487 len1 += (n = c->vv->varint_size(c->u.e_xpack.rmap[i])), r |= n;
1488 len += (n = c->vv->varint_put32_blk(b, c->vv->varint_size(c->u.e_xpack.nbits)
1489 + c->vv->varint_size(c->u.e_xpack.nval)
1490 + len1 + len2)); r |= n;
1491
1492 // The map and sub-codec
1493 len += (n = c->vv->varint_put32_blk(b, c->u.e_xpack.nbits)); r |= n;
1494 len += (n = c->vv->varint_put32_blk(b, c->u.e_xpack.nval)); r |= n;
1495 for (i = 0; i < c->u.e_xpack.nval; i++)
1496 len += (n = c->vv->varint_put32_blk(b, c->u.e_xpack.rmap[i])), r |= n;
1497
1498 BLOCK_APPEND(b, BLOCK_DATA(tb), BLOCK_SIZE(tb));
1499
1500 cram_free_block(tb);
1501
1502 return r > 0 ? len + len2 : -1;
1503
1504 block_err:
1505 return -1;
1506 }
1507
1508 // Same as cram_beta_encode_long
cram_xpack_encode_long(cram_slice * slice,cram_codec * c,char * in,int in_size)1509 int cram_xpack_encode_long(cram_slice *slice, cram_codec *c,
1510 char *in, int in_size) {
1511 int64_t *syms = (int64_t *)in;
1512 int i, r = 0;
1513
1514 for (i = 0; i < in_size; i++)
1515 r |= store_bits_MSB(c->out, c->u.e_xpack.map[syms[i]], c->u.e_xpack.nbits);
1516
1517 return r;
1518 }
1519
cram_xpack_encode_int(cram_slice * slice,cram_codec * c,char * in,int in_size)1520 int cram_xpack_encode_int(cram_slice *slice, cram_codec *c,
1521 char *in, int in_size) {
1522 int *syms = (int *)in;
1523 int i, r = 0;
1524
1525 for (i = 0; i < in_size; i++)
1526 r |= store_bits_MSB(c->out, c->u.e_xpack.map[syms[i]], c->u.e_xpack.nbits);
1527
1528 return r;
1529 }
1530
cram_xpack_encode_char(cram_slice * slice,cram_codec * c,char * in,int in_size)1531 int cram_xpack_encode_char(cram_slice *slice, cram_codec *c,
1532 char *in, int in_size) {
1533 BLOCK_APPEND(c->out, in, in_size);
1534 return 0;
1535
1536 block_err:
1537 return -1;
1538 }
1539
cram_xpack_encode_free(cram_codec * c)1540 void cram_xpack_encode_free(cram_codec *c) {
1541 if (!c) return;
1542
1543 if (c->u.e_xpack.sub_codec)
1544 c->u.e_xpack.sub_codec->free(c->u.e_xpack.sub_codec);
1545
1546 cram_free_block(c->out);
1547
1548 free(c);
1549 }
1550
cram_xpack_encode_init(cram_stats * st,enum cram_encoding codec,enum cram_external_type option,void * dat,int version,varint_vec * vv)1551 cram_codec *cram_xpack_encode_init(cram_stats *st,
1552 enum cram_encoding codec,
1553 enum cram_external_type option,
1554 void *dat,
1555 int version, varint_vec *vv) {
1556 cram_codec *c;
1557
1558 if (!(c = malloc(sizeof(*c))))
1559 return NULL;
1560
1561 c->codec = E_XPACK;
1562 c->free = cram_xpack_encode_free;
1563 if (option == E_LONG)
1564 c->encode = cram_xpack_encode_long;
1565 else if (option == E_INT)
1566 c->encode = cram_xpack_encode_int;
1567 else
1568 c->encode = cram_xpack_encode_char;
1569 c->store = cram_xpack_encode_store;
1570 c->flush = cram_xpack_encode_flush;
1571
1572 cram_xpack_encoder *e = (cram_xpack_encoder *)dat;
1573 c->u.e_xpack.nbits = e->nbits;
1574 c->u.e_xpack.nval = e->nval;
1575 c->u.e_xpack.sub_codec = cram_encoder_init(e->sub_encoding, NULL,
1576 E_BYTE_ARRAY, e->sub_codec_dat,
1577 version, vv);
1578
1579 // Initialise fwd and rev maps
1580 memcpy(c->u.e_xpack.map, e->map, sizeof(e->map)); // P,A,C,K to 0,1,2,3
1581 int i, n;
1582 for (i = n = 0; i < 256; i++)
1583 if (e->map[i] != -1)
1584 c->u.e_xpack.rmap[n++] = i; // 0,1,2,3 to P,A,C,K
1585 if (n != e->nval) {
1586 fprintf(stderr, "Incorrectly specified number of map items in PACK\n");
1587 return NULL;
1588 }
1589
1590 return c;
1591 }
1592
1593 /*
1594 * ---------------------------------------------------------------------------
1595 * XDELTA: subtract successive values, zig-zag to turn +/- to + only,
1596 * and then var-int encode the result.
1597 *
1598 * This also has the additional requirement that the data series is not
1599 * interleaved with another, permitting efficient encoding and decoding
1600 * of all elements enmasse instead of needing to only extract the bits
1601 * necessary per item.
1602 */
1603
zigzag8(int8_t x)1604 static uint8_t zigzag8 (int8_t x) { return (x << 1) ^ (x >> 7); }
zigzag16(int16_t x)1605 static uint16_t zigzag16(int16_t x) { return (x << 1) ^ (x >> 15); }
zigzag32(int32_t x)1606 static uint32_t zigzag32(int32_t x) { return (x << 1) ^ (x >> 31); }
1607
1608 //static int8_t unzigzag8 (uint8_t x) { return (x >> 1) ^ -(x & 1); }
unzigzag16(uint16_t x)1609 static int16_t unzigzag16(uint16_t x) { return (x >> 1) ^ -(x & 1); }
unzigzag32(uint32_t x)1610 static int32_t unzigzag32(uint32_t x) { return (x >> 1) ^ -(x & 1); }
1611
cram_xdelta_decode_long(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)1612 int cram_xdelta_decode_long(cram_slice *slice, cram_codec *c, cram_block *in, char *out, int *out_size) {
1613 return -1;
1614 }
1615
cram_xdelta_decode_int(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)1616 int cram_xdelta_decode_int(cram_slice *slice, cram_codec *c, cram_block *in, char *out, int *out_size) {
1617 // Slow value-by-value method for now
1618 uint32_t *out32 = (uint32_t *)out;
1619 int i;
1620 for (i = 0; i < *out_size; i++) {
1621 uint32_t v;
1622 int one = 1;
1623 if (c->u.e_xdelta.sub_codec->decode(slice, c->u.e_xdelta.sub_codec, in,
1624 (char *)&v, &one) < 0)
1625 return -1;
1626 uint32_t d = unzigzag32(v);
1627 c->u.xdelta.last = out32[i] = d + c->u.xdelta.last;
1628 }
1629
1630 return 0;
1631 }
1632
cram_xdelta_decode_expand_char(cram_slice * slice,cram_codec * c)1633 static int cram_xdelta_decode_expand_char(cram_slice *slice, cram_codec *c) {
1634 return -1;
1635 }
1636
cram_xdelta_decode_char(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)1637 int cram_xdelta_decode_char(cram_slice *slice, cram_codec *c, cram_block *in, char *out, int *out_size) {
1638 return -1;
1639 }
1640
le_int2(int16_t i)1641 static inline int16_t le_int2(int16_t i) {
1642 int16_t s;
1643 i16_to_le(i, (uint8_t *)&s);
1644 return s;
1645 }
1646
cram_xdelta_decode_block(cram_slice * slice,cram_codec * c,cram_block * in,char * out_,int * out_size)1647 int cram_xdelta_decode_block(cram_slice *slice, cram_codec *c, cram_block *in,
1648 char *out_, int *out_size) {
1649 cram_block *out = (cram_block *)out_;
1650 cram_block *b = c->u.e_xdelta.sub_codec->get_block(slice, c->u.e_xdelta.sub_codec);
1651 int i = 0;
1652
1653 const int w = c->u.xdelta.word_size;
1654 uint32_t npad = (w - *out_size%w)%w;
1655 uint32_t out_sz = *out_size + npad;
1656 c->u.xdelta.last = 0; // reset for each new array
1657
1658 for (i = 0; i < out_sz; i += w) {
1659 uint16_t v;
1660 // Need better interface
1661 char *cp = (char *)b->data + b->byte;
1662 char *cp_end = (char *)b->data + b->uncomp_size;
1663 int err = 0;
1664 v = c->vv->varint_get32(&cp, cp_end, &err);
1665 if (err)
1666 return -1;
1667 b->byte = cp - (char *)b->data;
1668
1669 switch(w) {
1670 case 2: {
1671 int16_t d = unzigzag16(v), z;
1672 c->u.xdelta.last = d + c->u.xdelta.last;
1673 z = le_int2(c->u.xdelta.last);
1674 BLOCK_APPEND(out, &z, 2-npad);
1675 npad = 0;
1676 break;
1677 }
1678 default:
1679 fprintf(stderr, "Unsupported word size by XDELTA\n");
1680 return -1;
1681 }
1682 }
1683
1684 return 0;
1685
1686 block_err:
1687 return -1;
1688 }
1689
cram_xdelta_decode_free(cram_codec * c)1690 void cram_xdelta_decode_free(cram_codec *c) {
1691 if (!c) return;
1692
1693 if (c->u.xdelta.sub_codec)
1694 c->u.xdelta.sub_codec->free(c->u.xdelta.sub_codec);
1695
1696 free(c);
1697 }
1698
cram_xdelta_decode_size(cram_slice * slice,cram_codec * c)1699 int cram_xdelta_decode_size(cram_slice *slice, cram_codec *c) {
1700 cram_xdelta_decode_expand_char(slice, c);
1701 return slice->block_by_id[512 + c->codec_id]->uncomp_size;
1702 }
1703
cram_xdelta_get_block(cram_slice * slice,cram_codec * c)1704 cram_block *cram_xdelta_get_block(cram_slice *slice, cram_codec *c) {
1705 cram_xdelta_decode_expand_char(slice, c);
1706 return slice->block_by_id[512 + c->codec_id];
1707 }
1708
cram_xdelta_decode_init(cram_block_compression_hdr * hdr,char * data,int size,enum cram_encoding codec,enum cram_external_type option,int version,varint_vec * vv)1709 cram_codec *cram_xdelta_decode_init(cram_block_compression_hdr *hdr,
1710 char *data, int size,
1711 enum cram_encoding codec,
1712 enum cram_external_type option,
1713 int version, varint_vec *vv) {
1714 cram_codec *c;
1715 char *cp = data;
1716 char *endp = data+size;
1717
1718 if (!(c = calloc(1, sizeof(*c))))
1719 return NULL;
1720
1721 c->codec = E_XDELTA;
1722 if (option == E_LONG)
1723 c->decode = cram_xdelta_decode_long;
1724 else if (option == E_INT)
1725 c->decode = cram_xdelta_decode_int;
1726 else if (option == E_BYTE_ARRAY || option == E_BYTE)
1727 c->decode = cram_xdelta_decode_char;
1728 else if (option == E_BYTE_ARRAY_BLOCK) {
1729 option = E_BYTE_ARRAY;
1730 c->decode = cram_xdelta_decode_block;
1731 } else {
1732 free(c);
1733 return NULL;
1734 }
1735 c->free = cram_xdelta_decode_free;
1736 c->size = cram_xdelta_decode_size;
1737 c->get_block = cram_xdelta_get_block;
1738
1739 c->u.xdelta.word_size = vv->varint_get32(&cp, endp, NULL);
1740 c->u.xdelta.last = 0;
1741
1742 int encoding = vv->varint_get32(&cp, endp, NULL);
1743 int sub_size = vv->varint_get32(&cp, endp, NULL);
1744 if (sub_size < 0 || endp - cp < sub_size)
1745 goto malformed;
1746 c->u.xdelta.sub_codec = cram_decoder_init(hdr, encoding, cp, sub_size,
1747 option, version, vv);
1748 if (c->u.xdelta.sub_codec == NULL)
1749 goto malformed;
1750 cp += sub_size;
1751
1752 if (cp - data != size) {
1753 malformed:
1754 fprintf(stderr, "Malformed xdelta header stream\n");
1755 cram_xdelta_decode_free(c);
1756 return NULL;
1757 }
1758
1759 return c;
1760 }
1761
cram_xdelta_encode_flush(cram_codec * c)1762 int cram_xdelta_encode_flush(cram_codec *c) {
1763 int r = -1;
1764 cram_block *b = cram_new_block(0, 0);
1765 if (!b)
1766 return -1;
1767
1768 switch (c->u.e_xdelta.word_size) {
1769 case 2: {
1770 // Delta + zigzag transform.
1771 // Subtracting two 8-bit values has a 9-bit result (-255 to 255).
1772 // However think of it as turning a wheel clockwise or anti-clockwise.
1773 // If it has 256 gradations then a -ve rotation followed by a +ve
1774 // rotation of the same amount reverses it regardless.
1775 //
1776 // Similarly the zig-zag transformation doesn't invent any extra bits,
1777 // so the entire thing can be done in-situ. This may permit faster
1778 // SIMD loops if we break apart the steps.
1779
1780 // uint16_t last = 0, d;
1781 // for (i = 0; i < n; i++) {
1782 // d = io[i] - last;
1783 // last = io[i];
1784 // io[i] = zigzag16(vd);
1785 // }
1786
1787 // --- vs ---
1788
1789 // for (i = n-1; i >= 1; i--)
1790 // io[i] -= io[i-1];
1791 // for (i = 0; i < n; i++)
1792 // io[i] = zigzag16(io[i]);
1793
1794 // varint: need array variant for speed here.
1795 // With zig-zag
1796 int i, n = BLOCK_SIZE(c->out)/2;;
1797 uint16_t *dat = (uint16_t *)BLOCK_DATA(c->out), last = 0;
1798
1799 if (n*2 < BLOCK_SIZE(c->out)) {
1800 // half word
1801 last = *(uint8_t *)dat;
1802 c->vv->varint_put32_blk(b, zigzag16(last));
1803 dat = (uint16_t *)(((uint8_t *)dat)+1);
1804 }
1805
1806 for (i = 0; i < n; i++) {
1807 uint16_t d = dat[i] - last; // possibly unaligned
1808 last = dat[i];
1809 c->vv->varint_put32_blk(b, zigzag16(d));
1810 }
1811
1812 break;
1813 }
1814
1815 case 4: {
1816 int i, n = BLOCK_SIZE(c->out)/4;;
1817 uint32_t *dat = (uint32_t *)BLOCK_DATA(c->out), last = 0;
1818
1819 for (i = 0; i < n; i++) {
1820 uint32_t d = dat[i] - last;
1821 last = dat[i];
1822 c->vv->varint_put32_blk(b, zigzag32(d));
1823 }
1824
1825 break;
1826 }
1827
1828 case 1: {
1829 int i, n = BLOCK_SIZE(c->out);;
1830 uint8_t *dat = (uint8_t *)BLOCK_DATA(c->out), last = 0;
1831
1832 for (i = 0; i < n; i++) {
1833 uint32_t d = dat[i] - last;
1834 last = dat[i];
1835 c->vv->varint_put32_blk(b, zigzag8(d));
1836 }
1837
1838 break;
1839 }
1840
1841 default:
1842 goto err;
1843 }
1844
1845 if (c->u.e_xdelta.sub_codec->encode(NULL, c->u.e_xdelta.sub_codec,
1846 (char *)b->data, b->byte))
1847 goto err;
1848
1849 r = 0;
1850
1851 err:
1852 cram_free_block(b);
1853 return r;
1854
1855 }
1856
cram_xdelta_encode_store(cram_codec * c,cram_block * b,char * prefix,int version)1857 int cram_xdelta_encode_store(cram_codec *c, cram_block *b,
1858 char *prefix, int version) {
1859 int len = 0, r = 0, n;
1860
1861 if (prefix) {
1862 size_t l = strlen(prefix);
1863 BLOCK_APPEND(b, prefix, l);
1864 len += l;
1865 }
1866
1867 // Store sub-codec
1868 cram_codec *tc = c->u.e_xdelta.sub_codec;
1869 cram_block *tb = cram_new_block(0, 0);
1870 if (!tb)
1871 return -1;
1872 int len2 = tc->store(tc, tb, NULL, version);
1873
1874 len += (n = c->vv->varint_put32_blk(b, c->codec)); r |= n;
1875
1876 // codec length
1877 len += (n = c->vv->varint_put32_blk(b, c->vv->varint_size(c->u.e_xdelta.word_size)
1878 + len2)); r |= n;
1879
1880 // This and sub-codec
1881 len += (n = c->vv->varint_put32_blk(b, c->u.e_xdelta.word_size)); r |= n;
1882 BLOCK_APPEND(b, BLOCK_DATA(tb), BLOCK_SIZE(tb));
1883
1884 cram_free_block(tb);
1885
1886 return r > 0 ? len + len2 : -1;
1887
1888 block_err:
1889 return -1;
1890 }
1891
1892 // Same as cram_beta_encode_long
cram_xdelta_encode_long(cram_slice * slice,cram_codec * c,char * in,int in_size)1893 int cram_xdelta_encode_long(cram_slice *slice, cram_codec *c,
1894 char *in, int in_size) {
1895 return -1;
1896 }
1897
cram_xdelta_encode_int(cram_slice * slice,cram_codec * c,char * in,int in_size)1898 int cram_xdelta_encode_int(cram_slice *slice, cram_codec *c,
1899 char *in, int in_size) {
1900 return -1;
1901 }
1902
cram_xdelta_encode_char(cram_slice * slice,cram_codec * c,char * in,int in_size)1903 int cram_xdelta_encode_char(cram_slice *slice, cram_codec *c,
1904 char *in, int in_size) {
1905 char *dat = malloc(in_size*5);
1906 if (!dat)
1907 return -1;
1908 char *cp = dat, *cp_end = dat + in_size*5;
1909
1910 c->u.e_xdelta.last = 0; // reset for each new array
1911 if (c->u.e_xdelta.word_size == 2) {
1912 int i, part;
1913
1914 part = in_size%2;
1915 if (part) {
1916 uint16_t z = in[0];
1917 c->u.e_xdelta.last = le_int2(z);
1918 cp += c->vv->varint_put32(cp, cp_end, zigzag16(c->u.e_xdelta.last));
1919 }
1920
1921 uint16_t *in16 = (uint16_t *)(in+part);
1922 for (i = 0; i < in_size/2; i++) {
1923 uint16_t d = le_int2(in16[i]) - c->u.e_xdelta.last;
1924 c->u.e_xdelta.last = le_int2(in16[i]);
1925 cp += c->vv->varint_put32(cp, cp_end, zigzag16(d));
1926 }
1927 }
1928 if (c->u.e_xdelta.sub_codec->encode(slice, c->u.e_xdelta.sub_codec,
1929 (char *)dat, cp-dat)) {
1930 free(dat);
1931 return -1;
1932 }
1933
1934 free(dat);
1935 return 0;
1936 }
1937
cram_xdelta_encode_free(cram_codec * c)1938 void cram_xdelta_encode_free(cram_codec *c) {
1939 if (!c) return;
1940
1941 if (c->u.e_xdelta.sub_codec)
1942 c->u.e_xdelta.sub_codec->free(c->u.e_xdelta.sub_codec);
1943
1944 cram_free_block(c->out);
1945
1946 free(c);
1947 }
1948
cram_xdelta_encode_init(cram_stats * st,enum cram_encoding codec,enum cram_external_type option,void * dat,int version,varint_vec * vv)1949 cram_codec *cram_xdelta_encode_init(cram_stats *st,
1950 enum cram_encoding codec,
1951 enum cram_external_type option,
1952 void *dat,
1953 int version, varint_vec *vv) {
1954 cram_codec *c;
1955
1956 if (!(c = malloc(sizeof(*c))))
1957 return NULL;
1958
1959 c->codec = E_XDELTA;
1960 c->free = cram_xdelta_encode_free;
1961 if (option == E_LONG)
1962 c->encode = cram_xdelta_encode_long;
1963 else if (option == E_INT)
1964 c->encode = cram_xdelta_encode_int;
1965 else
1966 c->encode = cram_xdelta_encode_char;
1967 c->store = cram_xdelta_encode_store;
1968 c->flush = cram_xdelta_encode_flush;
1969
1970 cram_xdelta_encoder *e = (cram_xdelta_encoder *)dat;
1971 c->u.e_xdelta.word_size = e->word_size;
1972 c->u.e_xdelta.last = 0;
1973 c->u.e_xdelta.sub_codec = cram_encoder_init(e->sub_encoding, NULL,
1974 E_BYTE_ARRAY,
1975 e->sub_codec_dat,
1976 version, vv);
1977
1978 return c;
1979 }
1980
1981 /*
1982 * ---------------------------------------------------------------------------
1983 * XRLE
1984 *
1985 * This also has the additional requirement that the data series is not
1986 * interleaved with another, permitting efficient encoding and decoding
1987 * of all elements enmasse instead of needing to only extract the bits
1988 * necessary per item.
1989 */
cram_xrle_decode_long(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)1990 int cram_xrle_decode_long(cram_slice *slice, cram_codec *c, cram_block *in, char *out, int *out_size) {
1991 // TODO if and when needed
1992 return -1;
1993 }
1994
cram_xrle_decode_int(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)1995 int cram_xrle_decode_int(cram_slice *slice, cram_codec *c, cram_block *in, char *out, int *out_size) {
1996 // TODO if and when needed
1997 return -1;
1998 }
1999
2000 // Expands an XRLE transform and caches result in slice->block_by_id[]
cram_xrle_decode_expand_char(cram_slice * slice,cram_codec * c)2001 static int cram_xrle_decode_expand_char(cram_slice *slice, cram_codec *c) {
2002 cram_block *b = slice->block_by_id[512 + c->codec_id];
2003 if (b)
2004 return 0;
2005
2006 b = slice->block_by_id[512 + c->codec_id] = cram_new_block(0, 0);
2007 if (!b)
2008 return -1;
2009 cram_block *lit_b = c->u.xrle.lit_codec->get_block(slice, c->u.xrle.lit_codec);
2010 if (!lit_b)
2011 return -1;
2012 unsigned char *lit_dat = lit_b->data;
2013 unsigned int lit_sz = lit_b->uncomp_size;
2014 unsigned int len_sz = c->u.xrle.len_codec->size(slice, c->u.xrle.len_codec);
2015
2016 cram_block *len_b = c->u.xrle.len_codec->get_block(slice, c->u.xrle.len_codec);
2017 if (!len_b)
2018 return -1;
2019 unsigned char *len_dat = len_b->data;
2020
2021 uint8_t rle_syms[256];
2022 int rle_nsyms = 0;
2023 int i;
2024 for (i = 0; i < 256; i++) {
2025 if (c->u.xrle.rep_score[i] > 0)
2026 rle_syms[rle_nsyms++] = i;
2027 }
2028
2029 uint64_t out_sz;
2030 int nb = var_get_u64(len_dat, len_dat+len_sz, &out_sz);
2031 if (!(b->data = malloc(out_sz)))
2032 return -1;
2033 rle_decode(lit_dat, lit_sz,
2034 len_dat+nb, len_sz-nb,
2035 rle_syms, rle_nsyms,
2036 b->data, &out_sz);
2037 b->uncomp_size = out_sz;
2038
2039 return 0;
2040 }
2041
cram_xrle_decode_size(cram_slice * slice,cram_codec * c)2042 int cram_xrle_decode_size(cram_slice *slice, cram_codec *c) {
2043 cram_xrle_decode_expand_char(slice, c);
2044 return slice->block_by_id[512 + c->codec_id]->uncomp_size;
2045 }
2046
cram_xrle_get_block(cram_slice * slice,cram_codec * c)2047 cram_block *cram_xrle_get_block(cram_slice *slice, cram_codec *c) {
2048 cram_xrle_decode_expand_char(slice, c);
2049 return slice->block_by_id[512 + c->codec_id];
2050 }
2051
cram_xrle_decode_char(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)2052 int cram_xrle_decode_char(cram_slice *slice, cram_codec *c, cram_block *in, char *out, int *out_size) {
2053 int n = *out_size;
2054
2055 cram_xrle_decode_expand_char(slice, c);
2056 cram_block *b = slice->block_by_id[512 + c->codec_id];
2057
2058 memcpy(out, b->data + b->idx, n);
2059 b->idx += n;
2060 return 0;
2061
2062 // Old code when not cached
2063 while (n > 0) {
2064 if (c->u.xrle.cur_len == 0) {
2065 unsigned char lit;
2066 int one = 1;
2067 if (c->u.xrle.lit_codec->decode(slice, c->u.xrle.lit_codec, in,
2068 (char *)&lit, &one) < 0)
2069 return -1;
2070 c->u.xrle.cur_lit = lit;
2071
2072 if (c->u.xrle.rep_score[lit] > 0) {
2073 if (c->u.xrle.len_codec->decode(slice, c->u.xrle.len_codec, in,
2074 (char *)&c->u.xrle.cur_len, &one) < 0)
2075 return -1;
2076 } // else cur_len still zero
2077 //else fprintf(stderr, "%d\n", lit);
2078
2079 c->u.xrle.cur_len++;
2080 }
2081
2082 if (n >= c->u.xrle.cur_len) {
2083 memset(out, c->u.xrle.cur_lit, c->u.xrle.cur_len);
2084 out += c->u.xrle.cur_len;
2085 n -= c->u.xrle.cur_len;
2086 c->u.xrle.cur_len = 0;
2087 } else {
2088 memset(out, c->u.xrle.cur_lit, n);
2089 out += n;
2090 c->u.xrle.cur_len -= n;
2091 n = 0;
2092 }
2093 }
2094
2095 return 0;
2096 }
2097
cram_xrle_decode_free(cram_codec * c)2098 void cram_xrle_decode_free(cram_codec *c) {
2099 if (!c) return;
2100
2101 if (c->u.xrle.len_codec)
2102 c->u.xrle.len_codec->free(c->u.xrle.len_codec);
2103
2104 if (c->u.xrle.lit_codec)
2105 c->u.xrle.lit_codec->free(c->u.xrle.lit_codec);
2106
2107 free(c);
2108 }
2109
cram_xrle_decode_init(cram_block_compression_hdr * hdr,char * data,int size,enum cram_encoding codec,enum cram_external_type option,int version,varint_vec * vv)2110 cram_codec *cram_xrle_decode_init(cram_block_compression_hdr *hdr,
2111 char *data, int size,
2112 enum cram_encoding codec,
2113 enum cram_external_type option,
2114 int version, varint_vec *vv) {
2115 cram_codec *c;
2116 char *cp = data;
2117 char *endp = data+size;
2118 int err = 0;
2119
2120 if (!(c = calloc(1, sizeof(*c))))
2121 return NULL;
2122
2123 c->codec = E_XRLE;
2124 if (option == E_LONG)
2125 c->decode = cram_xrle_decode_long;
2126 else if (option == E_INT)
2127 c->decode = cram_xrle_decode_int;
2128 else if (option == E_BYTE_ARRAY || option == E_BYTE)
2129 c->decode = cram_xrle_decode_char;
2130 else {
2131 fprintf(stderr, "BYTE_ARRAYs not supported by this codec\n");
2132 free(c);
2133 return NULL;
2134 }
2135 c->free = cram_xrle_decode_free;
2136 c->size = cram_xrle_decode_size;
2137 c->get_block = cram_xrle_get_block;
2138 c->u.xrle.cur_len = 0;
2139 c->u.xrle.cur_lit = -1;
2140
2141 // RLE map
2142 int i, j, nrle = vv->varint_get32(&cp, endp, &err);
2143 memset(c->u.xrle.rep_score, 0, 256*sizeof(*c->u.xrle.rep_score));
2144 for (i = 0; i < nrle && i < 256; i++) {
2145 j = vv->varint_get32(&cp, endp, &err);
2146 if (j >= 0 && j < 256)
2147 c->u.xrle.rep_score[j] = 1;
2148 }
2149
2150 // Length and literal sub encodings
2151 c->u.xrle.len_encoding = vv->varint_get32(&cp, endp, &err);
2152 int sub_size = vv->varint_get32(&cp, endp, &err);
2153 if (sub_size < 0 || endp - cp < sub_size)
2154 goto malformed;
2155 c->u.xrle.len_codec = cram_decoder_init(hdr, c->u.xrle.len_encoding,
2156 cp, sub_size, E_INT, version, vv);
2157 if (c->u.xrle.len_codec == NULL)
2158 goto malformed;
2159 cp += sub_size;
2160
2161 c->u.xrle.lit_encoding = vv->varint_get32(&cp, endp, &err);
2162 sub_size = vv->varint_get32(&cp, endp, &err);
2163 if (sub_size < 0 || endp - cp < sub_size)
2164 goto malformed;
2165 c->u.xrle.lit_codec = cram_decoder_init(hdr, c->u.xrle.lit_encoding,
2166 cp, sub_size, option, version, vv);
2167 if (c->u.xrle.lit_codec == NULL)
2168 goto malformed;
2169 cp += sub_size;
2170
2171 if (err)
2172 goto malformed;
2173
2174 return c;
2175
2176 malformed:
2177 fprintf(stderr, "Malformed xrle header stream\n");
2178 cram_xrle_decode_free(c);
2179 return NULL;
2180 }
2181
cram_xrle_encode_flush(cram_codec * c)2182 int cram_xrle_encode_flush(cram_codec *c) {
2183 uint8_t *out_lit, *out_len;
2184 uint64_t out_lit_size, out_len_size;
2185 uint8_t rle_syms[256];
2186 int rle_nsyms = 0, i;
2187
2188 for (i = 0; i < 256; i++)
2189 if (c->u.e_xrle.rep_score[i] > 0)
2190 rle_syms[rle_nsyms++] = i;
2191
2192 if (!c->u.e_xrle.to_flush) {
2193 c->u.e_xrle.to_flush = (char *)BLOCK_DATA(c->out);
2194 c->u.e_xrle.to_flush_size = BLOCK_SIZE(c->out);
2195 }
2196
2197 out_len = malloc(c->u.e_xrle.to_flush_size+8);
2198 if (!out_len)
2199 return -1;
2200
2201 int nb = var_put_u64(out_len, NULL, c->u.e_xrle.to_flush_size);
2202
2203 out_lit = rle_encode((uint8_t *)c->u.e_xrle.to_flush, c->u.e_xrle.to_flush_size,
2204 out_len+nb, &out_len_size,
2205 rle_syms, &rle_nsyms,
2206 NULL, &out_lit_size);
2207 out_len_size += nb;
2208
2209
2210 // TODO: can maybe "gift" the sub codec the data block, to remove
2211 // one level of memcpy.
2212 if (c->u.e_xrle.len_codec->encode(NULL,
2213 c->u.e_xrle.len_codec,
2214 (char *)out_len, out_len_size))
2215 return -1;
2216
2217 if (c->u.e_xrle.lit_codec->encode(NULL,
2218 c->u.e_xrle.lit_codec,
2219 (char *)out_lit, out_lit_size))
2220 return -1;
2221
2222 free(out_len);
2223 free(out_lit);
2224
2225 return 0;
2226 }
2227
cram_xrle_encode_store(cram_codec * c,cram_block * b,char * prefix,int version)2228 int cram_xrle_encode_store(cram_codec *c, cram_block *b,
2229 char *prefix, int version) {
2230 int len = 0, r = 0, n;
2231 cram_codec *tc;
2232 cram_block *b_rle, *b_len, *b_lit;
2233
2234 if (prefix) {
2235 size_t l = strlen(prefix);
2236 BLOCK_APPEND(b, prefix, l);
2237 len += l;
2238 }
2239
2240 // List of symbols to RLE
2241 b_rle = cram_new_block(0, 0);
2242 if (!b_rle)
2243 return -1;
2244 int i, nrle = 0, len1 = 0;
2245 for (i = 0; i < 256; i++) {
2246 if (c->u.e_xrle.rep_score[i] > 0) {
2247 nrle++;
2248 len1 += (n = c->vv->varint_put32_blk(b_rle,i)); r |= n;
2249 }
2250 }
2251
2252 // Store length and literal sub-codecs to get encoded length
2253 tc = c->u.e_xrle.len_codec;
2254 b_len = cram_new_block(0, 0);
2255 if (!b_len)
2256 return -1;
2257 int len2 = tc->store(tc, b_len, NULL, version);
2258
2259 tc = c->u.e_xrle.lit_codec;
2260 b_lit = cram_new_block(0, 0);
2261 if (!b_lit)
2262 return -1;
2263 int len3 = tc->store(tc, b_lit, NULL, version);
2264
2265 len += (n = c->vv->varint_put32_blk(b, c->codec)); r |= n;
2266 len += (n = c->vv->varint_put32_blk(b, len1 + len2 + len3
2267 + c->vv->varint_size(nrle))); r |= n;
2268 len += (n = c->vv->varint_put32_blk(b, nrle)); r |= n;
2269 BLOCK_APPEND(b, BLOCK_DATA(b_rle), BLOCK_SIZE(b_rle));
2270 BLOCK_APPEND(b, BLOCK_DATA(b_len), BLOCK_SIZE(b_len));
2271 BLOCK_APPEND(b, BLOCK_DATA(b_lit), BLOCK_SIZE(b_lit));
2272
2273 cram_free_block(b_rle);
2274 cram_free_block(b_len);
2275 cram_free_block(b_lit);
2276
2277 if (r > 0)
2278 return len + len1 + len2 + len3;
2279
2280 block_err:
2281 return -1;
2282 }
2283
cram_xrle_encode_long(cram_slice * slice,cram_codec * c,char * in,int in_size)2284 int cram_xrle_encode_long(cram_slice *slice, cram_codec *c,
2285 char *in, int in_size) {
2286 // TODO if and when needed
2287 return -1;
2288 }
2289
cram_xrle_encode_int(cram_slice * slice,cram_codec * c,char * in,int in_size)2290 int cram_xrle_encode_int(cram_slice *slice, cram_codec *c,
2291 char *in, int in_size) {
2292 // TODO if and when needed
2293 return -1;
2294 }
2295
cram_xrle_encode_char(cram_slice * slice,cram_codec * c,char * in,int in_size)2296 int cram_xrle_encode_char(cram_slice *slice, cram_codec *c,
2297 char *in, int in_size) {
2298 if (c->u.e_xrle.to_flush) {
2299 if (!c->out && !(c->out = cram_new_block(0, 0)))
2300 return -1;
2301 BLOCK_APPEND(c->out, c->u.e_xrle.to_flush, c->u.e_xrle.to_flush_size);
2302 c->u.e_xrle.to_flush = NULL;
2303 c->u.e_xrle.to_flush_size = 0;
2304 }
2305
2306 if (c->out && BLOCK_SIZE(c->out) > 0) {
2307 // Gathering data
2308 BLOCK_APPEND(c->out, in, in_size);
2309 return 0;
2310 }
2311
2312 // else cache copy of the data we're about to send to flush instead.
2313 c->u.e_xrle.to_flush = in;
2314 c->u.e_xrle.to_flush_size = in_size;
2315 return 0;
2316
2317 block_err:
2318 return -1;
2319 }
2320
cram_xrle_encode_free(cram_codec * c)2321 void cram_xrle_encode_free(cram_codec *c) {
2322 if (!c) return;
2323
2324 if (c->u.e_xrle.len_codec)
2325 c->u.e_xrle.len_codec->free(c->u.e_xrle.len_codec);
2326 if (c->u.e_xrle.lit_codec)
2327 c->u.e_xrle.lit_codec->free(c->u.e_xrle.lit_codec);
2328
2329 cram_free_block(c->out);
2330
2331 free(c);
2332 }
2333
cram_xrle_encode_init(cram_stats * st,enum cram_encoding codec,enum cram_external_type option,void * dat,int version,varint_vec * vv)2334 cram_codec *cram_xrle_encode_init(cram_stats *st,
2335 enum cram_encoding codec,
2336 enum cram_external_type option,
2337 void *dat,
2338 int version, varint_vec *vv) {
2339 cram_codec *c;
2340
2341 if (!(c = malloc(sizeof(*c))))
2342 return NULL;
2343
2344 c->codec = E_XRLE;
2345 c->free = cram_xrle_encode_free;
2346 if (option == E_LONG)
2347 c->encode = cram_xrle_encode_long;
2348 else if (option == E_INT)
2349 c->encode = cram_xrle_encode_int;
2350 else
2351 c->encode = cram_xrle_encode_char;
2352 c->store = cram_xrle_encode_store;
2353 c->flush = cram_xrle_encode_flush;
2354
2355 cram_xrle_encoder *e = (cram_xrle_encoder *)dat;
2356
2357 c->u.e_xrle.len_codec = cram_encoder_init(e->len_encoding, NULL,
2358 E_BYTE, e->len_dat,
2359 version, vv);
2360 c->u.e_xrle.lit_codec = cram_encoder_init(e->lit_encoding, NULL,
2361 E_BYTE, e->lit_dat,
2362 version, vv);
2363 c->u.e_xrle.cur_lit = -1;
2364 c->u.e_xrle.cur_len = -1;
2365 c->u.e_xrle.to_flush = NULL;
2366 c->u.e_xrle.to_flush_size = 0;
2367
2368 memcpy(c->u.e_xrle.rep_score, e->rep_score, 256*sizeof(*c->u.e_xrle.rep_score));
2369
2370 return c;
2371 }
2372
2373 /*
2374 * ---------------------------------------------------------------------------
2375 * SUBEXP
2376 */
cram_subexp_decode(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)2377 int cram_subexp_decode(cram_slice *slice, cram_codec *c, cram_block *in, char *out, int *out_size) {
2378 int32_t *out_i = (int32_t *)out;
2379 int n, count;
2380 int k = c->u.subexp.k;
2381
2382 for (count = 0, n = *out_size; count < n; count++) {
2383 int i = 0, tail;
2384 int val;
2385
2386 /* Get number of 1s */
2387 //while (get_bit_MSB(in) == 1) i++;
2388 i = get_one_bits_MSB(in);
2389 if (i < 0 || cram_not_enough_bits(in, i > 0 ? i + k - 1 : k))
2390 return -1;
2391 /*
2392 * Val is
2393 * i > 0: 2^(k+i-1) + k+i-1 bits
2394 * i = 0: k bits
2395 */
2396 if (i) {
2397 tail = i + k-1;
2398 val = 0;
2399 while (tail) {
2400 //val = val<<1; val |= get_bit_MSB(in);
2401 GET_BIT_MSB(in, val);
2402 tail--;
2403 }
2404 val += 1 << (i + k-1);
2405 } else {
2406 tail = k;
2407 val = 0;
2408 while (tail) {
2409 //val = val<<1; val |= get_bit_MSB(in);
2410 GET_BIT_MSB(in, val);
2411 tail--;
2412 }
2413 }
2414
2415 out_i[count] = val - c->u.subexp.offset;
2416 }
2417
2418 return 0;
2419 }
2420
cram_subexp_decode_free(cram_codec * c)2421 void cram_subexp_decode_free(cram_codec *c) {
2422 if (c)
2423 free(c);
2424 }
2425
cram_subexp_decode_init(cram_block_compression_hdr * hdr,char * data,int size,enum cram_encoding codec,enum cram_external_type option,int version,varint_vec * vv)2426 cram_codec *cram_subexp_decode_init(cram_block_compression_hdr *hdr,
2427 char *data, int size,
2428 enum cram_encoding codec,
2429 enum cram_external_type option,
2430 int version, varint_vec *vv) {
2431 cram_codec *c;
2432 char *cp = data;
2433
2434 if (option != E_INT) {
2435 hts_log_error("This codec only supports INT encodings");
2436 return NULL;
2437 }
2438
2439 if (!(c = malloc(sizeof(*c))))
2440 return NULL;
2441
2442 c->codec = E_SUBEXP;
2443 c->decode = cram_subexp_decode;
2444 c->free = cram_subexp_decode_free;
2445 c->u.subexp.k = -1;
2446
2447 c->u.subexp.offset = vv->varint_get32(&cp, data + size, NULL);
2448 c->u.subexp.k = vv->varint_get32(&cp, data + size, NULL);
2449
2450 if (cp - data != size || c->u.subexp.k < 0) {
2451 hts_log_error("Malformed subexp header stream");
2452 free(c);
2453 return NULL;
2454 }
2455
2456 return c;
2457 }
2458
2459 /*
2460 * ---------------------------------------------------------------------------
2461 * GAMMA
2462 */
cram_gamma_decode(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)2463 int cram_gamma_decode(cram_slice *slice, cram_codec *c, cram_block *in, char *out, int *out_size) {
2464 int32_t *out_i = (int32_t *)out;
2465 int i, n;
2466
2467 for (i = 0, n = *out_size; i < n; i++) {
2468 int nz = 0;
2469 int val;
2470 //while (get_bit_MSB(in) == 0) nz++;
2471 nz = get_zero_bits_MSB(in);
2472 if (cram_not_enough_bits(in, nz))
2473 return -1;
2474 val = 1;
2475 while (nz > 0) {
2476 //val <<= 1; val |= get_bit_MSB(in);
2477 GET_BIT_MSB(in, val);
2478 nz--;
2479 }
2480
2481 out_i[i] = val - c->u.gamma.offset;
2482 }
2483
2484 return 0;
2485 }
2486
cram_gamma_decode_free(cram_codec * c)2487 void cram_gamma_decode_free(cram_codec *c) {
2488 if (c)
2489 free(c);
2490 }
2491
cram_gamma_decode_init(cram_block_compression_hdr * hdr,char * data,int size,enum cram_encoding codec,enum cram_external_type option,int version,varint_vec * vv)2492 cram_codec *cram_gamma_decode_init(cram_block_compression_hdr *hdr,
2493 char *data, int size,
2494 enum cram_encoding codec,
2495 enum cram_external_type option,
2496 int version, varint_vec *vv) {
2497 cram_codec *c = NULL;
2498 char *cp = data;
2499
2500 if (option != E_INT) {
2501 hts_log_error("This codec only supports INT encodings");
2502 return NULL;
2503 }
2504
2505 if (size < 1)
2506 goto malformed;
2507
2508 if (!(c = malloc(sizeof(*c))))
2509 return NULL;
2510
2511 c->codec = E_GAMMA;
2512 c->decode = cram_gamma_decode;
2513 c->free = cram_gamma_decode_free;
2514
2515 c->u.gamma.offset = vv->varint_get32(&cp, data+size, NULL);
2516
2517 if (cp - data != size)
2518 goto malformed;
2519
2520 return c;
2521
2522 malformed:
2523 hts_log_error("Malformed gamma header stream");
2524 free(c);
2525 return NULL;
2526 }
2527
2528 /*
2529 * ---------------------------------------------------------------------------
2530 * HUFFMAN
2531 */
2532
code_sort(const void * vp1,const void * vp2)2533 static int code_sort(const void *vp1, const void *vp2) {
2534 const cram_huffman_code *c1 = (const cram_huffman_code *)vp1;
2535 const cram_huffman_code *c2 = (const cram_huffman_code *)vp2;
2536
2537 if (c1->len != c2->len)
2538 return c1->len - c2->len;
2539 else
2540 return c1->symbol < c2->symbol ? -1 : (c1->symbol > c2->symbol ? 1 : 0);
2541 }
2542
cram_huffman_decode_free(cram_codec * c)2543 void cram_huffman_decode_free(cram_codec *c) {
2544 if (!c)
2545 return;
2546
2547 if (c->u.huffman.codes)
2548 free(c->u.huffman.codes);
2549 free(c);
2550 }
2551
cram_huffman_decode_null(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)2552 int cram_huffman_decode_null(cram_slice *slice, cram_codec *c,
2553 cram_block *in, char *out, int *out_size) {
2554 return -1;
2555 }
2556
cram_huffman_decode_char0(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)2557 int cram_huffman_decode_char0(cram_slice *slice, cram_codec *c,
2558 cram_block *in, char *out, int *out_size) {
2559 int i, n;
2560
2561 if (!out)
2562 return 0;
2563
2564 /* Special case of 0 length codes */
2565 for (i = 0, n = *out_size; i < n; i++) {
2566 out[i] = c->u.huffman.codes[0].symbol;
2567 }
2568 return 0;
2569 }
2570
cram_huffman_decode_char(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)2571 int cram_huffman_decode_char(cram_slice *slice, cram_codec *c,
2572 cram_block *in, char *out, int *out_size) {
2573 int i, n, ncodes = c->u.huffman.ncodes;
2574 const cram_huffman_code * const codes = c->u.huffman.codes;
2575
2576 for (i = 0, n = *out_size; i < n; i++) {
2577 int idx = 0;
2578 int val = 0, len = 0, last_len = 0;
2579
2580 for (;;) {
2581 int dlen = codes[idx].len - last_len;
2582 if (cram_not_enough_bits(in, dlen))
2583 return -1;
2584
2585 //val <<= dlen;
2586 //val |= get_bits_MSB(in, dlen);
2587 //last_len = (len += dlen);
2588
2589 last_len = (len += dlen);
2590 for (; dlen; dlen--) GET_BIT_MSB(in, val);
2591
2592 idx = val - codes[idx].p;
2593 if (idx >= ncodes || idx < 0)
2594 return -1;
2595
2596 if (codes[idx].code == val && codes[idx].len == len) {
2597 if (out) out[i] = codes[idx].symbol;
2598 break;
2599 }
2600 }
2601 }
2602
2603 return 0;
2604 }
2605
cram_huffman_decode_int0(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)2606 int cram_huffman_decode_int0(cram_slice *slice, cram_codec *c,
2607 cram_block *in, char *out, int *out_size) {
2608 int32_t *out_i = (int32_t *)out;
2609 int i, n;
2610 const cram_huffman_code * const codes = c->u.huffman.codes;
2611
2612 /* Special case of 0 length codes */
2613 for (i = 0, n = *out_size; i < n; i++) {
2614 out_i[i] = codes[0].symbol;
2615 }
2616 return 0;
2617 }
2618
cram_huffman_decode_int(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)2619 int cram_huffman_decode_int(cram_slice *slice, cram_codec *c,
2620 cram_block *in, char *out, int *out_size) {
2621 int32_t *out_i = (int32_t *)out;
2622 int i, n, ncodes = c->u.huffman.ncodes;
2623 const cram_huffman_code * const codes = c->u.huffman.codes;
2624
2625 for (i = 0, n = *out_size; i < n; i++) {
2626 int idx = 0;
2627 int val = 0, len = 0, last_len = 0;
2628
2629 // Now one bit at a time for remaining checks
2630 for (;;) {
2631 int dlen = codes[idx].len - last_len;
2632 if (cram_not_enough_bits(in, dlen))
2633 return -1;
2634
2635 //val <<= dlen;
2636 //val |= get_bits_MSB(in, dlen);
2637 //last_len = (len += dlen);
2638
2639 last_len = (len += dlen);
2640 for (; dlen; dlen--) GET_BIT_MSB(in, val);
2641
2642 idx = val - codes[idx].p;
2643 if (idx >= ncodes || idx < 0)
2644 return -1;
2645
2646 if (codes[idx].code == val && codes[idx].len == len) {
2647 out_i[i] = codes[idx].symbol;
2648 break;
2649 }
2650 }
2651 }
2652
2653 return 0;
2654 }
2655
cram_huffman_decode_long0(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)2656 int cram_huffman_decode_long0(cram_slice *slice, cram_codec *c,
2657 cram_block *in, char *out, int *out_size) {
2658 int64_t *out_i = (int64_t *)out;
2659 int i, n;
2660 const cram_huffman_code * const codes = c->u.huffman.codes;
2661
2662 /* Special case of 0 length codes */
2663 for (i = 0, n = *out_size; i < n; i++) {
2664 out_i[i] = codes[0].symbol;
2665 }
2666 return 0;
2667 }
2668
cram_huffman_decode_long(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)2669 int cram_huffman_decode_long(cram_slice *slice, cram_codec *c,
2670 cram_block *in, char *out, int *out_size) {
2671 int64_t *out_i = (int64_t *)out;
2672 int i, n, ncodes = c->u.huffman.ncodes;
2673 const cram_huffman_code * const codes = c->u.huffman.codes;
2674
2675 for (i = 0, n = *out_size; i < n; i++) {
2676 int idx = 0;
2677 int val = 0, len = 0, last_len = 0;
2678
2679 // Now one bit at a time for remaining checks
2680 for (;;) {
2681 int dlen = codes[idx].len - last_len;
2682 if (cram_not_enough_bits(in, dlen))
2683 return -1;
2684
2685 //val <<= dlen;
2686 //val |= get_bits_MSB(in, dlen);
2687 //last_len = (len += dlen);
2688
2689 last_len = (len += dlen);
2690 for (; dlen; dlen--) GET_BIT_MSB(in, val);
2691
2692 idx = val - codes[idx].p;
2693 if (idx >= ncodes || idx < 0)
2694 return -1;
2695
2696 if (codes[idx].code == val && codes[idx].len == len) {
2697 out_i[i] = codes[idx].symbol;
2698 break;
2699 }
2700 }
2701 }
2702
2703 return 0;
2704 }
2705
2706 /*
2707 * Initialises a huffman decoder from an encoding data stream.
2708 */
cram_huffman_decode_init(cram_block_compression_hdr * hdr,char * data,int size,enum cram_encoding codec,enum cram_external_type option,int version,varint_vec * vv)2709 cram_codec *cram_huffman_decode_init(cram_block_compression_hdr *hdr,
2710 char *data, int size,
2711 enum cram_encoding codec,
2712 enum cram_external_type option,
2713 int version, varint_vec *vv) {
2714 int32_t ncodes = 0, i, j;
2715 char *cp = data, *data_end = &data[size];
2716 cram_codec *h;
2717 cram_huffman_code *codes = NULL;
2718 int32_t val, last_len, max_len = 0;
2719 uint32_t max_val; // needs one more bit than val
2720 const int max_code_bits = sizeof(val) * 8 - 1;
2721 int err = 0;
2722
2723 if (option == E_BYTE_ARRAY_BLOCK) {
2724 hts_log_error("BYTE_ARRAYs not supported by this codec");
2725 return NULL;
2726 }
2727
2728 ncodes = vv->varint_get32(&cp, data_end, &err);
2729 if (ncodes < 0) {
2730 hts_log_error("Invalid number of symbols in huffman stream");
2731 return NULL;
2732 }
2733 if (ncodes >= SIZE_MAX / sizeof(*codes)) {
2734 errno = ENOMEM;
2735 return NULL;
2736 }
2737
2738 h = calloc(1, sizeof(*h));
2739 if (!h)
2740 return NULL;
2741
2742 h->codec = E_HUFFMAN;
2743 h->free = cram_huffman_decode_free;
2744
2745 h->u.huffman.ncodes = ncodes;
2746 h->u.huffman.option = option;
2747 if (ncodes) {
2748 codes = h->u.huffman.codes = malloc(ncodes * sizeof(*codes));
2749 if (!codes) {
2750 free(h);
2751 return NULL;
2752 }
2753 } else {
2754 codes = h->u.huffman.codes = NULL;
2755 }
2756
2757 /* Read symbols and bit-lengths */
2758 if (option == E_LONG) {
2759 for (i = 0; i < ncodes; i++)
2760 codes[i].symbol = vv->varint_get64(&cp, data_end, &err);
2761 } else if (option == E_INT || option == E_BYTE) {
2762 for (i = 0; i < ncodes; i++)
2763 codes[i].symbol = vv->varint_get32(&cp, data_end, &err);
2764 } else {
2765 goto malformed;
2766 }
2767
2768 if (err)
2769 goto malformed;
2770
2771 i = vv->varint_get32(&cp, data_end, &err);
2772 if (i != ncodes)
2773 goto malformed;
2774
2775 if (ncodes == 0) {
2776 /* NULL huffman stream. Ensure it returns an error if
2777 anything tries to use it. */
2778 h->decode = cram_huffman_decode_null;
2779 return h;
2780 }
2781
2782 for (i = 0; i < ncodes; i++) {
2783 codes[i].len = vv->varint_get32(&cp, data_end, &err);
2784 if (err)
2785 break;
2786 if (codes[i].len < 0) {
2787 hts_log_error("Huffman code length (%d) is negative", codes[i].len);
2788 goto malformed;
2789 }
2790 if (max_len < codes[i].len)
2791 max_len = codes[i].len;
2792 }
2793 if (err || cp - data != size || max_len >= ncodes)
2794 goto malformed;
2795
2796 /* 31 is max. bits available in val */
2797 if (max_len > max_code_bits) {
2798 hts_log_error("Huffman code length (%d) is greater "
2799 "than maximum supported (%d)", max_len, max_code_bits);
2800 goto malformed;
2801 }
2802
2803 /* Sort by bit length and then by symbol value */
2804 qsort(codes, ncodes, sizeof(*codes), code_sort);
2805
2806 /* Assign canonical codes */
2807 val = -1, last_len = 0, max_val = 0;
2808 for (i = 0; i < ncodes; i++) {
2809 val++;
2810 if (val > max_val)
2811 goto malformed;
2812
2813 if (codes[i].len > last_len) {
2814 val <<= (codes[i].len - last_len);
2815 last_len = codes[i].len;
2816 max_val = (1U << codes[i].len) - 1;
2817 }
2818 codes[i].code = val;
2819 }
2820
2821 /*
2822 * Compute the next starting point, offset by the i'th value.
2823 * For example if codes 10, 11, 12, 13 are 30, 31, 32, 33 then
2824 * codes[10..13].p = 30 - 10.
2825 */
2826 last_len = 0;
2827 for (i = j = 0; i < ncodes; i++) {
2828 if (codes[i].len > last_len) {
2829 j = codes[i].code - i;
2830 last_len = codes[i].len;
2831 }
2832 codes[i].p = j;
2833 }
2834
2835 // puts("==HUFF LEN==");
2836 // for (i = 0; i <= last_len+1; i++) {
2837 // printf("len %d=%d prefix %d\n", i, h->u.huffman.lengths[i], h->u.huffman.prefix[i]);
2838 // }
2839 // puts("===HUFFMAN CODES===");
2840 // for (i = 0; i < ncodes; i++) {
2841 // int j;
2842 // printf("%d: %d %d %d ", i, codes[i].symbol, codes[i].len, codes[i].code);
2843 // j = codes[i].len;
2844 // while (j) {
2845 // putchar(codes[i].code & (1 << --j) ? '1' : '0');
2846 // }
2847 // printf(" %d\n", codes[i].code);
2848 // }
2849
2850 if (option == E_BYTE || option == E_BYTE_ARRAY) {
2851 if (h->u.huffman.codes[0].len == 0)
2852 h->decode = cram_huffman_decode_char0;
2853 else
2854 h->decode = cram_huffman_decode_char;
2855 } else if (option == E_LONG || option == E_SLONG) {
2856 if (h->u.huffman.codes[0].len == 0)
2857 h->decode = cram_huffman_decode_long0;
2858 else
2859 h->decode = cram_huffman_decode_long;
2860 } else if (option == E_INT || option == E_SINT || option == E_BYTE) {
2861 if (h->u.huffman.codes[0].len == 0)
2862 h->decode = cram_huffman_decode_int0;
2863 else
2864 h->decode = cram_huffman_decode_int;
2865 } else {
2866 return NULL;
2867 }
2868
2869 return (cram_codec *)h;
2870
2871 malformed:
2872 hts_log_error("Malformed huffman header stream");
2873 free(codes);
2874 free(h);
2875 return NULL;
2876 }
2877
cram_huffman_encode_char0(cram_slice * slice,cram_codec * c,char * in,int in_size)2878 int cram_huffman_encode_char0(cram_slice *slice, cram_codec *c,
2879 char *in, int in_size) {
2880 return 0;
2881 }
2882
cram_huffman_encode_char(cram_slice * slice,cram_codec * c,char * in,int in_size)2883 int cram_huffman_encode_char(cram_slice *slice, cram_codec *c,
2884 char *in, int in_size) {
2885 int i, code, len, r = 0;
2886 unsigned char *syms = (unsigned char *)in;
2887
2888 while (in_size--) {
2889 int sym = *syms++;
2890 if (sym >= -1 && sym < MAX_HUFF) {
2891 i = c->u.e_huffman.val2code[sym+1];
2892 assert(c->u.e_huffman.codes[i].symbol == sym);
2893 code = c->u.e_huffman.codes[i].code;
2894 len = c->u.e_huffman.codes[i].len;
2895 } else {
2896 /* Slow - use a lookup table for when sym < MAX_HUFF? */
2897 for (i = 0; i < c->u.e_huffman.nvals; i++) {
2898 if (c->u.e_huffman.codes[i].symbol == sym)
2899 break;
2900 }
2901 if (i == c->u.e_huffman.nvals)
2902 return -1;
2903
2904 code = c->u.e_huffman.codes[i].code;
2905 len = c->u.e_huffman.codes[i].len;
2906 }
2907
2908 r |= store_bits_MSB(c->out, code, len);
2909 }
2910
2911 return r;
2912 }
2913
cram_huffman_encode_int0(cram_slice * slice,cram_codec * c,char * in,int in_size)2914 int cram_huffman_encode_int0(cram_slice *slice, cram_codec *c,
2915 char *in, int in_size) {
2916 return 0;
2917 }
2918
cram_huffman_encode_int(cram_slice * slice,cram_codec * c,char * in,int in_size)2919 int cram_huffman_encode_int(cram_slice *slice, cram_codec *c,
2920 char *in, int in_size) {
2921 int i, code, len, r = 0;
2922 int *syms = (int *)in;
2923
2924 while (in_size--) {
2925 int sym = *syms++;
2926
2927 if (sym >= -1 && sym < MAX_HUFF) {
2928 i = c->u.e_huffman.val2code[sym+1];
2929 assert(c->u.e_huffman.codes[i].symbol == sym);
2930 code = c->u.e_huffman.codes[i].code;
2931 len = c->u.e_huffman.codes[i].len;
2932 } else {
2933 /* Slow - use a lookup table for when sym < MAX_HUFFMAN_SYM? */
2934 for (i = 0; i < c->u.e_huffman.nvals; i++) {
2935 if (c->u.e_huffman.codes[i].symbol == sym)
2936 break;
2937 }
2938 if (i == c->u.e_huffman.nvals)
2939 return -1;
2940
2941 code = c->u.e_huffman.codes[i].code;
2942 len = c->u.e_huffman.codes[i].len;
2943 }
2944
2945 r |= store_bits_MSB(c->out, code, len);
2946 }
2947
2948 return r;
2949 }
2950
cram_huffman_encode_long0(cram_slice * slice,cram_codec * c,char * in,int in_size)2951 int cram_huffman_encode_long0(cram_slice *slice, cram_codec *c,
2952 char *in, int in_size) {
2953 return 0;
2954 }
2955
cram_huffman_encode_long(cram_slice * slice,cram_codec * c,char * in,int in_size)2956 int cram_huffman_encode_long(cram_slice *slice, cram_codec *c,
2957 char *in, int in_size) {
2958 int i, code, len, r = 0;
2959 int64_t *syms = (int64_t *)in;
2960
2961 while (in_size--) {
2962 int sym = *syms++;
2963
2964 if (sym >= -1 && sym < MAX_HUFF) {
2965 i = c->u.e_huffman.val2code[sym+1];
2966 assert(c->u.e_huffman.codes[i].symbol == sym);
2967 code = c->u.e_huffman.codes[i].code;
2968 len = c->u.e_huffman.codes[i].len;
2969 } else {
2970 /* Slow - use a lookup table for when sym < MAX_HUFFMAN_SYM? */
2971 for (i = 0; i < c->u.e_huffman.nvals; i++) {
2972 if (c->u.e_huffman.codes[i].symbol == sym)
2973 break;
2974 }
2975 if (i == c->u.e_huffman.nvals)
2976 return -1;
2977
2978 code = c->u.e_huffman.codes[i].code;
2979 len = c->u.e_huffman.codes[i].len;
2980 }
2981
2982 r |= store_bits_MSB(c->out, code, len);
2983 }
2984
2985 return r;
2986 }
2987
cram_huffman_encode_free(cram_codec * c)2988 void cram_huffman_encode_free(cram_codec *c) {
2989 if (!c)
2990 return;
2991
2992 if (c->u.e_huffman.codes)
2993 free(c->u.e_huffman.codes);
2994 free(c);
2995 }
2996
2997 /*
2998 * Encodes a huffman tree.
2999 * Returns number of bytes written.
3000 */
cram_huffman_encode_store(cram_codec * c,cram_block * b,char * prefix,int version)3001 int cram_huffman_encode_store(cram_codec *c, cram_block *b, char *prefix,
3002 int version) {
3003 int i, len = 0, r = 0, n;
3004 cram_huffman_code *codes = c->u.e_huffman.codes;
3005 /*
3006 * Up to code length 127 means 2.5e+26 bytes of data required (worst
3007 * case huffman tree needs symbols with freqs matching the Fibonacci
3008 * series). So guaranteed 1 byte per code.
3009 *
3010 * Symbols themselves could be 5 bytes (eg -1 is 5 bytes in itf8).
3011 *
3012 * Therefore 6*ncodes + 5 + 5 + 1 + 5 is max memory
3013 */
3014 char *tmp = malloc(6*c->u.e_huffman.nvals+16);
3015 char *tp = tmp, *tpend = tmp+6*c->u.e_huffman.nvals+16;
3016
3017 if (!tmp)
3018 return -1;
3019
3020 if (prefix) {
3021 size_t l = strlen(prefix);
3022 BLOCK_APPEND(b, prefix, l);
3023 len += l;
3024 }
3025
3026 tp += c->vv->varint_put32(tp, tpend, c->u.e_huffman.nvals);
3027 if (c->u.e_huffman.option == E_LONG) {
3028 for (i = 0; i < c->u.e_huffman.nvals; i++) {
3029 tp += c->vv->varint_put64(tp, tpend, codes[i].symbol);
3030 }
3031 } else if (c->u.e_huffman.option == E_SLONG) {
3032 for (i = 0; i < c->u.e_huffman.nvals; i++) {
3033 tp += c->vv->varint_put64s(tp, tpend, codes[i].symbol);
3034 }
3035 } else if (c->u.e_huffman.option == E_INT || c->u.e_huffman.option == E_BYTE) {
3036 for (i = 0; i < c->u.e_huffman.nvals; i++) {
3037 tp += c->vv->varint_put32(tp, tpend, codes[i].symbol);
3038 }
3039 } else if (c->u.e_huffman.option == E_SINT) {
3040 for (i = 0; i < c->u.e_huffman.nvals; i++) {
3041 tp += c->vv->varint_put32s(tp, tpend, codes[i].symbol);
3042 }
3043 } else {
3044 return -1;
3045 }
3046
3047 tp += c->vv->varint_put32(tp, tpend, c->u.e_huffman.nvals);
3048 for (i = 0; i < c->u.e_huffman.nvals; i++)
3049 tp += c->vv->varint_put32(tp, tpend, codes[i].len);
3050
3051 len += (n = c->vv->varint_put32_blk(b, c->codec)); r |= n;
3052 len += (n = c->vv->varint_put32_blk(b, tp-tmp)); r |= n;
3053 BLOCK_APPEND(b, tmp, tp-tmp);
3054 len += tp-tmp;
3055
3056 free(tmp);
3057
3058 if (r > 0)
3059 return len;
3060
3061 block_err:
3062 return -1;
3063 }
3064
cram_huffman_encode_init(cram_stats * st,enum cram_encoding codec,enum cram_external_type option,void * dat,int version,varint_vec * vv)3065 cram_codec *cram_huffman_encode_init(cram_stats *st,
3066 enum cram_encoding codec,
3067 enum cram_external_type option,
3068 void *dat,
3069 int version, varint_vec *vv) {
3070 int *vals = NULL, *freqs = NULL, *lens = NULL, code, len;
3071 int *new_vals, *new_freqs;
3072 int i, max_val = 0, min_val = INT_MAX, k;
3073 size_t nvals, vals_alloc = 0;
3074 cram_codec *c;
3075 cram_huffman_code *codes;
3076
3077 c = malloc(sizeof(*c));
3078 if (!c)
3079 return NULL;
3080 c->codec = E_HUFFMAN;
3081
3082 /* Count number of unique symbols */
3083 for (nvals = i = 0; i < MAX_STAT_VAL; i++) {
3084 if (!st->freqs[i])
3085 continue;
3086 if (nvals >= vals_alloc) {
3087 vals_alloc = vals_alloc ? vals_alloc*2 : 1024;
3088 new_vals = realloc(vals, vals_alloc * sizeof(int));
3089 if (!new_vals) goto nomem;
3090 vals = new_vals;
3091 new_freqs = realloc(freqs, vals_alloc * sizeof(int));
3092 if (!new_freqs) goto nomem;
3093 freqs = new_freqs;
3094 }
3095 vals[nvals] = i;
3096 freqs[nvals] = st->freqs[i];
3097 assert(st->freqs[i] > 0);
3098 if (max_val < i) max_val = i;
3099 if (min_val > i) min_val = i;
3100 nvals++;
3101 }
3102 if (st->h) {
3103 khint_t k;
3104
3105 for (k = kh_begin(st->h); k != kh_end(st->h); k++) {
3106 if (!kh_exist(st->h, k))
3107 continue;
3108 if (nvals >= vals_alloc) {
3109 vals_alloc = vals_alloc ? vals_alloc*2 : 1024;
3110 new_vals = realloc(vals, vals_alloc * sizeof(int));
3111 if (!new_vals) goto nomem;
3112 vals = new_vals;
3113 new_freqs = realloc(freqs, vals_alloc * sizeof(int));
3114 if (!new_freqs) goto nomem;
3115 freqs = new_freqs;
3116 }
3117 vals[nvals]= kh_key(st->h, k);
3118 freqs[nvals] = kh_val(st->h, k);
3119 assert(freqs[nvals] > 0);
3120 if (max_val < i) max_val = i;
3121 if (min_val > i) min_val = i;
3122 nvals++;
3123 }
3124 }
3125
3126 assert(nvals > 0);
3127
3128 new_freqs = realloc(freqs, 2*nvals*sizeof(*freqs));
3129 if (!new_freqs) goto nomem;
3130 freqs = new_freqs;
3131 lens = calloc(2*nvals, sizeof(*lens));
3132 if (!lens) goto nomem;
3133
3134 /* Inefficient, use pointers to form chain so we can insert and maintain
3135 * a sorted list? This is currently O(nvals^2) complexity.
3136 */
3137 for (;;) {
3138 int low1 = INT_MAX, low2 = INT_MAX;
3139 int ind1 = 0, ind2 = 0;
3140 for (i = 0; i < nvals; i++) {
3141 if (freqs[i] < 0)
3142 continue;
3143 if (low1 > freqs[i])
3144 low2 = low1, ind2 = ind1, low1 = freqs[i], ind1 = i;
3145 else if (low2 > freqs[i])
3146 low2 = freqs[i], ind2 = i;
3147 }
3148 if (low2 == INT_MAX)
3149 break;
3150
3151 freqs[nvals] = low1 + low2;
3152 lens[ind1] = nvals;
3153 lens[ind2] = nvals;
3154 freqs[ind1] *= -1;
3155 freqs[ind2] *= -1;
3156 nvals++;
3157 }
3158 nvals = nvals/2+1;
3159
3160 /* Assign lengths */
3161 for (i = 0; i < nvals; i++) {
3162 int code_len = 0;
3163 for (k = lens[i]; k; k = lens[k])
3164 code_len++;
3165 lens[i] = code_len;
3166 freqs[i] *= -1;
3167 //fprintf(stderr, "%d / %d => %d\n", vals[i], freqs[i], lens[i]);
3168 }
3169
3170
3171 /* Sort, need in a struct */
3172 if (!(codes = malloc(nvals * sizeof(*codes))))
3173 goto nomem;
3174 for (i = 0; i < nvals; i++) {
3175 codes[i].symbol = vals[i];
3176 codes[i].len = lens[i];
3177 }
3178 qsort(codes, nvals, sizeof(*codes), code_sort);
3179
3180 /*
3181 * Generate canonical codes from lengths.
3182 * Sort by length.
3183 * Start with 0.
3184 * Every new code of same length is +1.
3185 * Every new code of new length is +1 then <<1 per extra length.
3186 *
3187 * /\
3188 * a/\
3189 * /\/\
3190 * bcd/\
3191 * ef
3192 *
3193 * a 1 0
3194 * b 3 4 (0+1)<<2
3195 * c 3 5
3196 * d 3 6
3197 * e 4 14 (6+1)<<1
3198 * f 5 15
3199 */
3200 code = 0; len = codes[0].len;
3201 for (i = 0; i < nvals; i++) {
3202 while (len != codes[i].len) {
3203 code<<=1;
3204 len++;
3205 }
3206 codes[i].code = code++;
3207
3208 if (codes[i].symbol >= -1 && codes[i].symbol < MAX_HUFF)
3209 c->u.e_huffman.val2code[codes[i].symbol+1] = i;
3210
3211 //fprintf(stderr, "sym %d, code %d, len %d\n",
3212 // codes[i].symbol, codes[i].code, codes[i].len);
3213 }
3214
3215 free(lens);
3216 free(vals);
3217 free(freqs);
3218
3219 c->u.e_huffman.codes = codes;
3220 c->u.e_huffman.nvals = nvals;
3221 c->u.e_huffman.option = option;
3222
3223 c->free = cram_huffman_encode_free;
3224 if (option == E_BYTE || option == E_BYTE_ARRAY) {
3225 if (c->u.e_huffman.codes[0].len == 0)
3226 c->encode = cram_huffman_encode_char0;
3227 else
3228 c->encode = cram_huffman_encode_char;
3229 } else if (option == E_INT || option == E_SINT) {
3230 if (c->u.e_huffman.codes[0].len == 0)
3231 c->encode = cram_huffman_encode_int0;
3232 else
3233 c->encode = cram_huffman_encode_int;
3234 } else if (option == E_LONG || option == E_SLONG) {
3235 if (c->u.e_huffman.codes[0].len == 0)
3236 c->encode = cram_huffman_encode_long0;
3237 else
3238 c->encode = cram_huffman_encode_long;
3239 } else {
3240 return NULL;
3241 }
3242 c->store = cram_huffman_encode_store;
3243 c->flush = NULL;
3244
3245 return c;
3246
3247 nomem:
3248 hts_log_error("Out of memory");
3249 free(vals);
3250 free(freqs);
3251 free(lens);
3252 free(c);
3253 return NULL;
3254 }
3255
3256 /*
3257 * ---------------------------------------------------------------------------
3258 * BYTE_ARRAY_LEN
3259 */
cram_byte_array_len_decode(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)3260 int cram_byte_array_len_decode(cram_slice *slice, cram_codec *c,
3261 cram_block *in, char *out,
3262 int *out_size) {
3263 /* Fetch length */
3264 int32_t len = 0, one = 1;
3265 int r;
3266
3267 r = c->u.byte_array_len.len_codec->decode(slice, c->u.byte_array_len.len_codec,
3268 in, (char *)&len, &one);
3269 //printf("ByteArray Len=%d\n", len);
3270
3271 if (!r && c->u.byte_array_len.val_codec && len >= 0) {
3272 r = c->u.byte_array_len.val_codec->decode(slice,
3273 c->u.byte_array_len.val_codec,
3274 in, out, &len);
3275 } else {
3276 return -1;
3277 }
3278
3279 *out_size = len;
3280
3281 return r;
3282 }
3283
cram_byte_array_len_decode_free(cram_codec * c)3284 void cram_byte_array_len_decode_free(cram_codec *c) {
3285 if (!c) return;
3286
3287 if (c->u.byte_array_len.len_codec)
3288 c->u.byte_array_len.len_codec->free(c->u.byte_array_len.len_codec);
3289
3290 if (c->u.byte_array_len.val_codec)
3291 c->u.byte_array_len.val_codec->free(c->u.byte_array_len.val_codec);
3292
3293 free(c);
3294 }
3295
cram_byte_array_len_decode_init(cram_block_compression_hdr * hdr,char * data,int size,enum cram_encoding codec,enum cram_external_type option,int version,varint_vec * vv)3296 cram_codec *cram_byte_array_len_decode_init(cram_block_compression_hdr *hdr,
3297 char *data, int size,
3298 enum cram_encoding codec,
3299 enum cram_external_type option,
3300 int version, varint_vec *vv) {
3301 cram_codec *c;
3302 char *cp = data;
3303 char *endp = data + size;
3304
3305 if (!(c = malloc(sizeof(*c))))
3306 return NULL;
3307
3308 c->codec = E_BYTE_ARRAY_LEN;
3309 c->decode = cram_byte_array_len_decode;
3310 c->free = cram_byte_array_len_decode_free;
3311 c->u.byte_array_len.len_codec = NULL;
3312 c->u.byte_array_len.val_codec = NULL;
3313
3314 int encoding = vv->varint_get32(&cp, endp, NULL);
3315 int sub_size = vv->varint_get32(&cp, endp, NULL);
3316 if (sub_size < 0 || endp - cp < sub_size)
3317 goto malformed;
3318 c->u.byte_array_len.len_codec = cram_decoder_init(hdr, encoding, cp, sub_size,
3319 E_INT, version, vv);
3320 if (c->u.byte_array_len.len_codec == NULL)
3321 goto no_codec;
3322 cp += sub_size;
3323
3324 encoding = vv->varint_get32(&cp, endp, NULL);
3325 sub_size = vv->varint_get32(&cp, endp, NULL);
3326 if (sub_size < 0 || endp - cp < sub_size)
3327 goto malformed;
3328 c->u.byte_array_len.val_codec = cram_decoder_init(hdr, encoding, cp, sub_size,
3329 option, version, vv);
3330 if (c->u.byte_array_len.val_codec == NULL)
3331 goto no_codec;
3332 cp += sub_size;
3333
3334 if (cp - data != size)
3335 goto malformed;
3336
3337 return c;
3338
3339 malformed:
3340 hts_log_error("Malformed byte_array_len header stream");
3341 no_codec:
3342 cram_byte_array_len_decode_free(c);
3343 return NULL;
3344 }
3345
cram_byte_array_len_encode(cram_slice * slice,cram_codec * c,char * in,int in_size)3346 int cram_byte_array_len_encode(cram_slice *slice, cram_codec *c,
3347 char *in, int in_size) {
3348 int32_t i32 = in_size;
3349 int r = 0;
3350
3351 r |= c->u.e_byte_array_len.len_codec->encode(slice,
3352 c->u.e_byte_array_len.len_codec,
3353 (char *)&i32, 1);
3354 r |= c->u.e_byte_array_len.val_codec->encode(slice,
3355 c->u.e_byte_array_len.val_codec,
3356 in, in_size);
3357 return r;
3358 }
3359
cram_byte_array_len_encode_free(cram_codec * c)3360 void cram_byte_array_len_encode_free(cram_codec *c) {
3361 if (!c)
3362 return;
3363
3364 if (c->u.e_byte_array_len.len_codec)
3365 c->u.e_byte_array_len.len_codec->free(c->u.e_byte_array_len.len_codec);
3366
3367 if (c->u.e_byte_array_len.val_codec)
3368 c->u.e_byte_array_len.val_codec->free(c->u.e_byte_array_len.val_codec);
3369
3370 free(c);
3371 }
3372
cram_byte_array_len_encode_store(cram_codec * c,cram_block * b,char * prefix,int version)3373 int cram_byte_array_len_encode_store(cram_codec *c, cram_block *b,
3374 char *prefix, int version) {
3375 int len = 0, len2, len3, r = 0, n;
3376 cram_codec *tc;
3377 cram_block *b_len = NULL, *b_val = NULL;
3378
3379 if (prefix) {
3380 size_t l = strlen(prefix);
3381 BLOCK_APPEND(b, prefix, l);
3382 len += l;
3383 }
3384
3385 tc = c->u.e_byte_array_len.len_codec;
3386 b_len = cram_new_block(0, 0);
3387 if (!b_len) goto block_err;
3388 len2 = tc->store(tc, b_len, NULL, version);
3389 if (len2 < 0) goto block_err;
3390
3391 tc = c->u.e_byte_array_len.val_codec;
3392 b_val = cram_new_block(0, 0);
3393 if (!b_val) goto block_err;
3394 len3 = tc->store(tc, b_val, NULL, version);
3395 if (len3 < 0) goto block_err;
3396
3397 len += (n = c->vv->varint_put32_blk(b, c->codec)); r |= n;
3398 len += (n = c->vv->varint_put32_blk(b, len2+len3)); r |= n;
3399 BLOCK_APPEND(b, BLOCK_DATA(b_len), BLOCK_SIZE(b_len));
3400 BLOCK_APPEND(b, BLOCK_DATA(b_val), BLOCK_SIZE(b_val));
3401
3402 cram_free_block(b_len);
3403 cram_free_block(b_val);
3404
3405 if (r > 0)
3406 return len + len2 + len3;
3407
3408 block_err:
3409 if (b_len) cram_free_block(b_len);
3410 if (b_val) cram_free_block(b_val);
3411 return -1;
3412 }
3413
cram_byte_array_len_encode_init(cram_stats * st,enum cram_encoding codec,enum cram_external_type option,void * dat,int version,varint_vec * vv)3414 cram_codec *cram_byte_array_len_encode_init(cram_stats *st,
3415 enum cram_encoding codec,
3416 enum cram_external_type option,
3417 void *dat,
3418 int version, varint_vec *vv) {
3419 cram_codec *c;
3420 cram_byte_array_len_encoder *e = (cram_byte_array_len_encoder *)dat;
3421
3422 c = malloc(sizeof(*c));
3423 if (!c)
3424 return NULL;
3425 c->codec = E_BYTE_ARRAY_LEN;
3426 c->free = cram_byte_array_len_encode_free;
3427 c->encode = cram_byte_array_len_encode;
3428 c->store = cram_byte_array_len_encode_store;
3429 c->flush = NULL;
3430
3431 c->u.e_byte_array_len.len_codec = cram_encoder_init(e->len_encoding,
3432 st, E_INT,
3433 e->len_dat,
3434 version, vv);
3435 c->u.e_byte_array_len.val_codec = cram_encoder_init(e->val_encoding,
3436 NULL, E_BYTE_ARRAY,
3437 e->val_dat,
3438 version, vv);
3439
3440 if (!c->u.e_byte_array_len.len_codec ||
3441 !c->u.e_byte_array_len.val_codec) {
3442 cram_byte_array_len_encode_free(c);
3443 return NULL;
3444 }
3445
3446 return c;
3447 }
3448
3449 /*
3450 * ---------------------------------------------------------------------------
3451 * BYTE_ARRAY_STOP
3452 */
cram_byte_array_stop_decode_char(cram_slice * slice,cram_codec * c,cram_block * in,char * out,int * out_size)3453 static int cram_byte_array_stop_decode_char(cram_slice *slice, cram_codec *c,
3454 cram_block *in, char *out,
3455 int *out_size) {
3456 char *cp, ch;
3457 cram_block *b = NULL;
3458
3459 b = cram_get_block_by_id(slice, c->u.byte_array_stop.content_id);
3460 if (!b)
3461 return *out_size?-1:0;
3462
3463 if (b->idx >= b->uncomp_size)
3464 return -1;
3465
3466 cp = (char *)b->data + b->idx;
3467 if (out) {
3468 while ((ch = *cp) != (char)c->u.byte_array_stop.stop) {
3469 if (cp - (char *)b->data >= b->uncomp_size)
3470 return -1;
3471 *out++ = ch;
3472 cp++;
3473 }
3474 } else {
3475 // Consume input, but produce no output
3476 while ((ch = *cp) != (char)c->u.byte_array_stop.stop) {
3477 if (cp - (char *)b->data >= b->uncomp_size)
3478 return -1;
3479 cp++;
3480 }
3481 }
3482
3483 *out_size = cp - (char *)(b->data + b->idx);
3484 b->idx = cp - (char *)b->data + 1;
3485
3486 return 0;
3487 }
3488
cram_byte_array_stop_decode_block(cram_slice * slice,cram_codec * c,cram_block * in,char * out_,int * out_size)3489 int cram_byte_array_stop_decode_block(cram_slice *slice, cram_codec *c,
3490 cram_block *in, char *out_,
3491 int *out_size) {
3492 cram_block *b;
3493 cram_block *out = (cram_block *)out_;
3494 unsigned char *cp, *cp_end;
3495 unsigned char stop;
3496
3497 b = cram_get_block_by_id(slice, c->u.byte_array_stop.content_id);
3498 if (!b)
3499 return *out_size?-1:0;
3500
3501 if (b->idx >= b->uncomp_size)
3502 return -1;
3503 cp = b->data + b->idx;
3504 cp_end = b->data + b->uncomp_size;
3505
3506 stop = c->u.byte_array_stop.stop;
3507 if (cp_end - cp < out->alloc - out->byte) {
3508 unsigned char *out_cp = BLOCK_END(out);
3509 while (cp != cp_end && *cp != stop)
3510 *out_cp++ = *cp++;
3511 BLOCK_SIZE(out) = out_cp - BLOCK_DATA(out);
3512 } else {
3513 unsigned char *cp_start;
3514 for (cp_start = cp; cp != cp_end && *cp != stop; cp++)
3515 ;
3516 BLOCK_APPEND(out, cp_start, cp - cp_start);
3517 BLOCK_GROW(out, cp - cp_start);
3518 }
3519
3520 *out_size = cp - (b->data + b->idx);
3521 b->idx = cp - b->data + 1;
3522
3523 return 0;
3524
3525 block_err:
3526 return -1;
3527 }
3528
cram_byte_array_stop_decode_free(cram_codec * c)3529 void cram_byte_array_stop_decode_free(cram_codec *c) {
3530 if (!c) return;
3531
3532 free(c);
3533 }
3534
cram_byte_array_stop_decode_init(cram_block_compression_hdr * hdr,char * data,int size,enum cram_encoding codec,enum cram_external_type option,int version,varint_vec * vv)3535 cram_codec *cram_byte_array_stop_decode_init(cram_block_compression_hdr *hdr,
3536 char *data, int size,
3537 enum cram_encoding codec,
3538 enum cram_external_type option,
3539 int version, varint_vec *vv) {
3540 cram_codec *c = NULL;
3541 unsigned char *cp = (unsigned char *)data;
3542 int err = 0;
3543
3544 if (size < (CRAM_MAJOR_VERS(version) == 1 ? 5 : 2))
3545 goto malformed;
3546
3547 if (!(c = malloc(sizeof(*c))))
3548 return NULL;
3549
3550 c->codec = E_BYTE_ARRAY_STOP;
3551 switch (option) {
3552 case E_BYTE_ARRAY_BLOCK:
3553 c->decode = cram_byte_array_stop_decode_block;
3554 break;
3555 case E_BYTE_ARRAY:
3556 c->decode = cram_byte_array_stop_decode_char;
3557 break;
3558 default:
3559 hts_log_error("The byte_array_stop codec only supports BYTE_ARRAYs");
3560 free(c);
3561 return NULL;
3562 }
3563 c->free = cram_byte_array_stop_decode_free;
3564
3565 c->u.byte_array_stop.stop = *cp++;
3566 if (CRAM_MAJOR_VERS(version) == 1) {
3567 c->u.byte_array_stop.content_id = cp[0] + (cp[1]<<8) + (cp[2]<<16)
3568 + ((unsigned int) cp[3]<<24);
3569 cp += 4;
3570 } else {
3571 c->u.byte_array_stop.content_id = vv->varint_get32((char **)&cp, data+size, &err);
3572 }
3573
3574 if ((char *)cp - data != size || err)
3575 goto malformed;
3576
3577 return c;
3578
3579 malformed:
3580 hts_log_error("Malformed byte_array_stop header stream");
3581 free(c);
3582 return NULL;
3583 }
3584
cram_byte_array_stop_encode(cram_slice * slice,cram_codec * c,char * in,int in_size)3585 int cram_byte_array_stop_encode(cram_slice *slice, cram_codec *c,
3586 char *in, int in_size) {
3587 BLOCK_APPEND(c->out, in, in_size);
3588 BLOCK_APPEND_CHAR(c->out, c->u.e_byte_array_stop.stop);
3589 return 0;
3590
3591 block_err:
3592 return -1;
3593 }
3594
cram_byte_array_stop_encode_free(cram_codec * c)3595 void cram_byte_array_stop_encode_free(cram_codec *c) {
3596 if (!c)
3597 return;
3598 free(c);
3599 }
3600
cram_byte_array_stop_encode_store(cram_codec * c,cram_block * b,char * prefix,int version)3601 int cram_byte_array_stop_encode_store(cram_codec *c, cram_block *b,
3602 char *prefix, int version) {
3603 int len = 0;
3604 char buf[20], *cp = buf;
3605
3606 if (prefix) {
3607 size_t l = strlen(prefix);
3608 BLOCK_APPEND(b, prefix, l);
3609 len += l;
3610 }
3611
3612 cp += c->vv->varint_put32(cp, buf+20, c->codec);
3613
3614 if (CRAM_MAJOR_VERS(version) == 1) {
3615 cp += c->vv->varint_put32(cp, buf+20, 5);
3616 *cp++ = c->u.e_byte_array_stop.stop;
3617 *cp++ = (c->u.e_byte_array_stop.content_id >> 0) & 0xff;
3618 *cp++ = (c->u.e_byte_array_stop.content_id >> 8) & 0xff;
3619 *cp++ = (c->u.e_byte_array_stop.content_id >> 16) & 0xff;
3620 *cp++ = (c->u.e_byte_array_stop.content_id >> 24) & 0xff;
3621 } else {
3622 cp += c->vv->varint_put32(cp, buf+20, 1 +
3623 c->vv->varint_size(c->u.e_byte_array_stop.content_id));
3624 *cp++ = c->u.e_byte_array_stop.stop;
3625 cp += c->vv->varint_put32(cp, buf+20, c->u.e_byte_array_stop.content_id);
3626 }
3627
3628 BLOCK_APPEND(b, buf, cp-buf);
3629 len += cp-buf;
3630
3631 return len;
3632
3633 block_err:
3634 return -1;
3635 }
3636
cram_byte_array_stop_encode_init(cram_stats * st,enum cram_encoding codec,enum cram_external_type option,void * dat,int version,varint_vec * vv)3637 cram_codec *cram_byte_array_stop_encode_init(cram_stats *st,
3638 enum cram_encoding codec,
3639 enum cram_external_type option,
3640 void *dat,
3641 int version, varint_vec *vv) {
3642 cram_codec *c;
3643
3644 c = malloc(sizeof(*c));
3645 if (!c)
3646 return NULL;
3647 c->codec = E_BYTE_ARRAY_STOP;
3648 c->free = cram_byte_array_stop_encode_free;
3649 c->encode = cram_byte_array_stop_encode;
3650 c->store = cram_byte_array_stop_encode_store;
3651 c->flush = NULL;
3652
3653 c->u.e_byte_array_stop.stop = ((int *)dat)[0];
3654 c->u.e_byte_array_stop.content_id = ((int *)dat)[1];
3655
3656 return c;
3657 }
3658
3659 /*
3660 * ---------------------------------------------------------------------------
3661 */
3662
cram_encoding2str(enum cram_encoding t)3663 const char *cram_encoding2str(enum cram_encoding t) {
3664 switch (t) {
3665 case E_NULL: return "NULL";
3666 case E_EXTERNAL: return "EXTERNAL";
3667 case E_GOLOMB: return "GOLOMB";
3668 case E_HUFFMAN: return "HUFFMAN";
3669 case E_BYTE_ARRAY_LEN: return "BYTE_ARRAY_LEN";
3670 case E_BYTE_ARRAY_STOP: return "BYTE_ARRAY_STOP";
3671 case E_BETA: return "BETA";
3672 case E_SUBEXP: return "SUBEXP";
3673 case E_GOLOMB_RICE: return "GOLOMB_RICE";
3674 case E_GAMMA: return "GAMMA";
3675
3676 case E_VARINT_UNSIGNED: return "VARINT_UNSIGNED";
3677 case E_VARINT_SIGNED: return "VARINT_SIGNED";
3678 case E_CONST_BYTE: return "CONST_BYTE";
3679 case E_CONST_INT: return "CONST_INT";
3680
3681 case E_NUM_CODECS:
3682 default: return "?";
3683 }
3684 }
3685
3686 static cram_codec *(*decode_init[])(cram_block_compression_hdr *hdr,
3687 char *data,
3688 int size,
3689 enum cram_encoding codec,
3690 enum cram_external_type option,
3691 int version, varint_vec *vv) = {
3692 // CRAM 3.0 valid codecs
3693 NULL, // null codec
3694 cram_external_decode_init,
3695 NULL, // golomb
3696 cram_huffman_decode_init,
3697 cram_byte_array_len_decode_init,
3698 cram_byte_array_stop_decode_init,
3699 cram_beta_decode_init,
3700 cram_subexp_decode_init,
3701 NULL, // golomb rice
3702 cram_gamma_decode_init,
3703
3704 // Gap between CRAM 3 and CRAM 4; 9 to 39 inclusive
3705 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
3706 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
3707 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
3708
3709 NULL, // was xbyte
3710 cram_varint_decode_init, // varint unsigned
3711 cram_varint_decode_init, // varint signed
3712 cram_const_decode_init, // const byte
3713 cram_const_decode_init, // const int
3714
3715 // Gap to CRAM 4 transfomrations; 45 to 49 inclusive
3716 NULL, NULL, NULL, NULL, NULL,
3717
3718 NULL, // xhuffman
3719 cram_xpack_decode_init,
3720 cram_xrle_decode_init,
3721 cram_xdelta_decode_init,
3722 };
3723
cram_decoder_init(cram_block_compression_hdr * hdr,enum cram_encoding codec,char * data,int size,enum cram_external_type option,int version,varint_vec * vv)3724 cram_codec *cram_decoder_init(cram_block_compression_hdr *hdr,
3725 enum cram_encoding codec,
3726 char *data, int size,
3727 enum cram_external_type option,
3728 int version, varint_vec *vv) {
3729 if (codec >= E_NULL && codec < E_NUM_CODECS && decode_init[codec]) {
3730 cram_codec *r = decode_init[codec](hdr, data, size, codec,
3731 option, version, vv);
3732 if (r) {
3733 r->vv = vv;
3734 r->codec_id = hdr->ncodecs++;
3735 }
3736 return r;
3737 } else {
3738 hts_log_error("Unimplemented codec of type %s", cram_encoding2str(codec));
3739 return NULL;
3740 }
3741 }
3742
3743 static cram_codec *(*encode_init[])(cram_stats *stx,
3744 enum cram_encoding codec,
3745 enum cram_external_type option,
3746 void *opt,
3747 int version, varint_vec *vv) = {
3748 // CRAM 3.0 valid codecs
3749 NULL, // null codec
3750 cram_external_encode_init, // int/bytes in cram 3, byte only in cram 4
3751 NULL, // golomb
3752 cram_huffman_encode_init,
3753 cram_byte_array_len_encode_init,
3754 cram_byte_array_stop_encode_init,
3755 cram_beta_encode_init,
3756 NULL, // subexponential (we support decode only)
3757 NULL, // golomb rice
3758 NULL, // gamma (we support decode only)
3759
3760 // Gap between CRAM 3 and CRAM 4; 9 to 39 inclusive
3761 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
3762 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
3763 NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
3764
3765 NULL, // was xbyte
3766 cram_varint_encode_init, // varint unsigned
3767 cram_varint_encode_init, // varint signed
3768 cram_const_encode_init, // const byte
3769 cram_const_encode_init, // const int
3770
3771 // Gap to CRAM 4 transfomrations; 45 to 49 inclusive
3772 NULL, NULL, NULL, NULL, NULL,
3773
3774 NULL, // xhuffman
3775 cram_xpack_encode_init,
3776 cram_xrle_encode_init,
3777 cram_xdelta_encode_init,
3778 };
3779
cram_encoder_init(enum cram_encoding codec,cram_stats * st,enum cram_external_type option,void * dat,int version,varint_vec * vv)3780 cram_codec *cram_encoder_init(enum cram_encoding codec,
3781 cram_stats *st,
3782 enum cram_external_type option,
3783 void *dat,
3784 int version, varint_vec *vv) {
3785 if (st && !st->nvals)
3786 return NULL;
3787
3788 // cram_stats_encoding assumes integer data, but if option
3789 // is E_BYTE then tweak the requested encoding. This ought
3790 // to be fixed in cram_stats_encoding instead.
3791 if (option == E_BYTE || option == E_BYTE_ARRAY ||
3792 option == E_BYTE_ARRAY_BLOCK) {
3793 if (codec == E_VARINT_SIGNED || codec == E_VARINT_UNSIGNED)
3794 codec = E_EXTERNAL;
3795 else if (codec == E_CONST_INT)
3796 codec = E_CONST_BYTE;
3797 }
3798
3799 if (encode_init[codec]) {
3800 cram_codec *r;
3801 if ((r = encode_init[codec](st, codec, option, dat, version, vv)))
3802 r->out = NULL;
3803 if (!r) {
3804 hts_log_error("Unable to initialise codec of type %s", cram_encoding2str(codec));
3805 return NULL;
3806 }
3807 r->vv = vv;
3808 return r;
3809 } else {
3810 hts_log_error("Unimplemented codec of type %s", cram_encoding2str(codec));
3811 abort();
3812 }
3813 }
3814
3815 /*
3816 * Returns the content_id used by this codec, also in id2 if byte_array_len.
3817 * Returns -1 for the CORE block and -2 for unneeded.
3818 * id2 is only filled out for BYTE_ARRAY_LEN which uses 2 codecs.
3819 */
cram_codec_to_id(cram_codec * c,int * id2)3820 int cram_codec_to_id(cram_codec *c, int *id2) {
3821 int bnum1, bnum2 = -2;
3822
3823 switch (c->codec) {
3824 case E_CONST_INT:
3825 case E_CONST_BYTE:
3826 bnum1 = -2; // no blocks used
3827
3828 case E_HUFFMAN:
3829 bnum1 = c->u.huffman.ncodes == 1 ? -2 : -1;
3830 break;
3831
3832 case E_GOLOMB:
3833 case E_BETA:
3834 case E_SUBEXP:
3835 case E_GOLOMB_RICE:
3836 case E_GAMMA:
3837 // CORE block
3838 bnum1 = -1;
3839 break;
3840
3841 case E_EXTERNAL:
3842 case E_VARINT_UNSIGNED:
3843 case E_VARINT_SIGNED:
3844 bnum1 = c->u.external.content_id;
3845 break;
3846
3847 case E_BYTE_ARRAY_LEN:
3848 bnum1 = cram_codec_to_id(c->u.byte_array_len.len_codec, NULL);
3849 bnum2 = cram_codec_to_id(c->u.byte_array_len.val_codec, NULL);
3850 break;
3851
3852 case E_BYTE_ARRAY_STOP:
3853 bnum1 = c->u.byte_array_stop.content_id;
3854 break;
3855
3856 case E_NULL:
3857 bnum1 = -2;
3858 break;
3859
3860 default:
3861 hts_log_error("Unknown codec type %d", c->codec);
3862 bnum1 = -1;
3863 }
3864
3865 if (id2)
3866 *id2 = bnum2;
3867 return bnum1;
3868 }
3869
3870
3871 /*
3872 * cram_codec structures are specialised for decoding or encoding.
3873 * Unfortunately this makes turning a decoder into an encoder (such as
3874 * when transcoding files) problematic.
3875 *
3876 * This function converts a cram decoder codec into an encoder version
3877 * in-place (ie it modifiers the codec itself).
3878 *
3879 * Returns 0 on success;
3880 * -1 on failure.
3881 */
cram_codec_decoder2encoder(cram_fd * fd,cram_codec * c)3882 int cram_codec_decoder2encoder(cram_fd *fd, cram_codec *c) {
3883 int j;
3884
3885 switch (c->codec) {
3886 case E_CONST_INT:
3887 case E_CONST_BYTE:
3888 // shares struct with decode
3889 c->store = cram_const_encode_store;
3890 break;
3891
3892 case E_EXTERNAL:
3893 // shares struct with decode
3894 c->free = cram_external_encode_free;
3895 c->store = cram_external_encode_store;
3896 if (c->decode == cram_external_decode_int)
3897 c->encode = cram_external_encode_int;
3898 else if (c->decode == cram_external_decode_long)
3899 c->encode = cram_external_encode_long;
3900 else if (c->decode == cram_external_decode_char)
3901 c->encode = cram_external_encode_char;
3902 else if (c->decode == cram_external_decode_block)
3903 c->encode = cram_external_encode_char;
3904 else
3905 return -1;
3906 break;
3907
3908 case E_VARINT_SIGNED:
3909 case E_VARINT_UNSIGNED:
3910 // shares struct with decode
3911 c->free = cram_varint_encode_free;
3912 c->store = cram_varint_encode_store;
3913 if (c->decode == cram_varint_decode_int)
3914 c->encode = cram_varint_encode_int;
3915 else if (c->decode == cram_varint_decode_sint)
3916 c->encode = cram_varint_encode_sint;
3917 else if (c->decode == cram_varint_decode_long)
3918 c->encode = cram_varint_encode_long;
3919 else if (c->decode == cram_varint_decode_slong)
3920 c->encode = cram_varint_encode_slong;
3921 else
3922 return -1;
3923 break;
3924
3925 case E_HUFFMAN: {
3926 // New structure, so switch.
3927 // FIXME: we huffman and e_huffman structs amended, we could
3928 // unify this.
3929 cram_codec *t = malloc(sizeof(*t));
3930 if (!t) return -1;
3931 t->vv = c->vv;
3932 t->codec = E_HUFFMAN;
3933 t->free = cram_huffman_encode_free;
3934 t->store = cram_huffman_encode_store;
3935 t->u.e_huffman.codes = c->u.huffman.codes;
3936 t->u.e_huffman.nvals = c->u.huffman.ncodes;
3937 t->u.e_huffman.option = c->u.huffman.option;
3938 for (j = 0; j < t->u.e_huffman.nvals; j++) {
3939 int32_t sym = t->u.e_huffman.codes[j].symbol;
3940 if (sym >= -1 && sym < MAX_HUFF)
3941 t->u.e_huffman.val2code[sym+1] = j;
3942 }
3943
3944 if (c->decode == cram_huffman_decode_char0)
3945 t->encode = cram_huffman_encode_char0;
3946 else if (c->decode == cram_huffman_decode_char)
3947 t->encode = cram_huffman_encode_char;
3948 else if (c->decode == cram_huffman_decode_int0)
3949 t->encode = cram_huffman_encode_int0;
3950 else if (c->decode == cram_huffman_decode_int)
3951 t->encode = cram_huffman_encode_int;
3952 else if (c->decode == cram_huffman_decode_long0)
3953 t->encode = cram_huffman_encode_long0;
3954 else if (c->decode == cram_huffman_decode_long)
3955 t->encode = cram_huffman_encode_long;
3956 else {
3957 free(t);
3958 return -1;
3959 }
3960 *c = *t;
3961 free(t);
3962 break;
3963 }
3964
3965 case E_BETA:
3966 // shares struct with decode
3967 c->free = cram_beta_encode_free;
3968 c->store = cram_beta_encode_store;
3969 if (c->decode == cram_beta_decode_int)
3970 c->encode = cram_beta_encode_int;
3971 else if (c->decode == cram_beta_decode_long)
3972 c->encode = cram_beta_encode_long;
3973 else if (c->decode == cram_beta_decode_char)
3974 c->encode = cram_beta_encode_char;
3975 else
3976 return -1;
3977 break;
3978
3979 case E_XPACK: {
3980 // shares struct with decode
3981 cram_codec t = *c;
3982 t.free = cram_xpack_encode_free;
3983 t.store = cram_xpack_encode_store;
3984 if (t.decode == cram_xpack_decode_long)
3985 t.encode = cram_xpack_encode_long;
3986 else if (t.decode == cram_xpack_decode_int)
3987 t.encode = cram_xpack_encode_int;
3988 else if (t.decode == cram_xpack_decode_char)
3989 t.encode = cram_xpack_encode_char;
3990 else
3991 return -1;
3992 t.u.e_xpack.sub_codec = t.u.xpack.sub_codec;
3993 if (cram_codec_decoder2encoder(fd, t.u.e_xpack.sub_codec) == -1)
3994 return -1;
3995 *c = t;
3996 break;
3997 }
3998
3999 case E_BYTE_ARRAY_LEN: {
4000 cram_codec *t = malloc(sizeof(*t));
4001 if (!t) return -1;
4002 t->vv = c->vv;
4003 t->codec = E_BYTE_ARRAY_LEN;
4004 t->free = cram_byte_array_len_encode_free;
4005 t->store = cram_byte_array_len_encode_store;
4006 t->encode = cram_byte_array_len_encode;
4007 t->u.e_byte_array_len.len_codec = c->u.byte_array_len.len_codec;
4008 t->u.e_byte_array_len.val_codec = c->u.byte_array_len.val_codec;
4009 if (cram_codec_decoder2encoder(fd, t->u.e_byte_array_len.len_codec) == -1 ||
4010 cram_codec_decoder2encoder(fd, t->u.e_byte_array_len.val_codec) == -1) {
4011 t->free(t);
4012 return -1;
4013 }
4014
4015 // {len,val}_{encoding,dat} are undefined, but unused.
4016 // Leaving them unset here means we can test that assertion.
4017 *c = *t;
4018 free(t);
4019 break;
4020 }
4021
4022 case E_BYTE_ARRAY_STOP:
4023 // shares struct with decode
4024 c->free = cram_byte_array_stop_encode_free;
4025 c->store = cram_byte_array_stop_encode_store;
4026 c->encode = cram_byte_array_stop_encode;
4027 break;
4028
4029 default:
4030 return -1;
4031 }
4032
4033 return 0;
4034 }
4035