Debian Codegraph @

bwa-apache2/rle.c

raw
1 #include <string.h>
2 #include <assert.h>
3 #include <stdlib.h>
4 #include <stdio.h>
5 #include "rle.h"
6
7 const uint8_t rle_auxtab[8] = { 0x01, 0x11, 0x21, 0x31, 0x03, 0x13, 0x07, 0x17 };
8
9 // insert symbol $a after $x symbols in $str; marginal counts added to $cnt; returns the size increase
10 int rle_insert_cached(uint8_t *block, int64_t x, int a, int64_t rl, int64_t cnt[6], const int64_t ec[6], int *beg, int64_t bc[6])
11 {
12 uint16_t *nptr = (uint16_t*)block;
13 int diff;
14
15 block += 2; // skip the first 2 counting bytes
16 if (*nptr == 0) {
17 memset(cnt, 0, 48);
18 diff = rle_enc1(block, a, rl);
19 } else {
20 uint8_t *p, *end = block + *nptr, *q;
21 int64_t pre, z, l = 0, tot, beg_l;
22 int c = -1, n_bytes = 0, n_bytes2, t = 0;
23 uint8_t tmp[24];
24 beg_l = bc[0] + bc[1] + bc[2] + bc[3] + bc[4] + bc[5];
25 tot = ec[0] + ec[1] + ec[2] + ec[3] + ec[4] + ec[5];
26 if (x < beg_l) {
27 beg_l = 0, *beg = 0;
28 memset(bc, 0, 48);
29 }
30 if (x == beg_l) {
31 p = q = block + (*beg); z = beg_l;
32 memcpy(cnt, bc, 48);
33 } else if (x - beg_l <= ((tot-beg_l)>>1) + ((tot-beg_l)>>3)) { // forward
34 z = beg_l; p = block + (*beg);
35 memcpy(cnt, bc, 48);
36 while (z < x) {
37 rle_dec1(p, c, l);
38 z += l; cnt[c] += l;
39 }
40 for (q = p - 1; *q>>6 == 2; --q);
41 } else { // backward
42 memcpy(cnt, ec, 48);
43 z = tot; p = end;
44 while (z >= x) {
45 --p;
46 if (*p>>6 != 2) {
47 l |= *p>>7? (int64_t)rle_auxtab[*p>>3&7]>>4 << t : *p>>3;
48 z -= l; cnt[*p&7] -= l;
49 l = 0; t = 0;
50 } else {
51 l |= (*p&0x3fL) << t;
52 t += 6;
53 }
54 }
55 q = p;
56 rle_dec1(p, c, l);
57 z += l; cnt[c] += l;
58 }
59 *beg = q - block;
60 memcpy(bc, cnt, 48);
61 bc[c] -= l;
62 n_bytes = p - q;
63 if (x == z && a != c && p < end) { // then try the next run
64 int tc;
65 int64_t tl;
66 q = p;
67 rle_dec1(q, tc, tl);
68 if (a == tc)
69 c = tc, n_bytes = q - p, l = tl, z += l, p = q, cnt[tc] += tl;
70 }
71 if (z != x) cnt[c] -= z - x;
72 pre = x - (z - l); p -= n_bytes;
73 if (a == c) { // insert to the same run
74 n_bytes2 = rle_enc1(tmp, c, l + rl);
75 } else if (x == z) { // at the end; append to the existing run
76 p += n_bytes; n_bytes = 0;
77 n_bytes2 = rle_enc1(tmp, a, rl);
78 } else { // break the current run
79 n_bytes2 = rle_enc1(tmp, c, pre);
80 n_bytes2 += rle_enc1(tmp + n_bytes2, a, rl);
81 n_bytes2 += rle_enc1(tmp + n_bytes2, c, l - pre);
82 }
83 if (n_bytes != n_bytes2 && end != p + n_bytes) // size changed
84 memmove(p + n_bytes2, p + n_bytes, end - p - n_bytes);
85 memcpy(p, tmp, n_bytes2);
86 diff = n_bytes2 - n_bytes;
87 }
88 return (*nptr += diff);
89 }
90
91 int rle_insert(uint8_t *block, int64_t x, int a, int64_t rl, int64_t cnt[6], const int64_t ec[6])
92 {
93 int beg = 0;
94 int64_t bc[6];
95 memset(bc, 0, 48);
96 return rle_insert_cached(block, x, a, rl, cnt, ec, &beg, bc);
97 }
98
99 void rle_split(uint8_t *block, uint8_t *new_block)
100 {
101 int n = *(uint16_t*)block;
102 uint8_t *end = block + 2 + n, *q = block + 2 + (n>>1);
103 while (*q>>6 == 2) --q;
104 memcpy(new_block + 2, q, end - q);
105 *(uint16_t*)new_block = end - q;
106 *(uint16_t*)block = q - block - 2;
107 }
108
109 void rle_count(const uint8_t *block, int64_t cnt[6])
110 {
111 const uint8_t *q = block + 2, *end = q + *(uint16_t*)block;
112 while (q < end) {
113 int c;
114 int64_t l;
115 rle_dec1(q, c, l);
116 cnt[c] += l;
117 }
118 }
119
120 void rle_print(const uint8_t *block, int expand)
121 {
122 const uint16_t *p = (const uint16_t*)block;
123 const uint8_t *q = block + 2, *end = block + 2 + *p;
124 while (q < end) {
125 int c;
126 int64_t l, x;
127 rle_dec1(q, c, l);
128 if (expand) for (x = 0; x < l; ++x) putchar("$ACGTN"[c]);
129 else printf("%c%ld", "$ACGTN"[c], (long)l);
130 }
131 putchar('\n');
132 }
133
134 void rle_rank2a(const uint8_t *block, int64_t x, int64_t y, int64_t *cx, int64_t *cy, const int64_t ec[6])
135 {
136 int a;
137 int64_t tot, cnt[6];
138 const uint8_t *p;
139
140 y = y >= x? y : x;
141 tot = ec[0] + ec[1] + ec[2] + ec[3] + ec[4] + ec[5];
142 if (tot == 0) return;
143 if (x <= (tot - y) + (tot>>3)) {
144 int c = 0;
145 int64_t l, z = 0;
146 memset(cnt, 0, 48);
147 p = block + 2;
148 while (z < x) {
149 rle_dec1(p, c, l);
150 z += l; cnt[c] += l;
151 }
152 for (a = 0; a != 6; ++a) cx[a] += cnt[a];
153 cx[c] -= z - x;
154 if (cy) {
155 while (z < y) {
156 rle_dec1(p, c, l);
157 z += l; cnt[c] += l;
158 }
159 for (a = 0; a != 6; ++a) cy[a] += cnt[a];
160 cy[c] -= z - y;
161 }
162 } else {
163 #define move_backward(_x) \
164 while (z >= (_x)) { \
165 --p; \
166 if (*p>>6 != 2) { \
167 l |= *p>>7? (int64_t)rle_auxtab[*p>>3&7]>>4 << t : *p>>3; \
168 z -= l; cnt[*p&7] -= l; \
169 l = 0; t = 0; \
170 } else { \
171 l |= (*p&0x3fL) << t; \
172 t += 6; \
173 } \
174 } \
175
176 int t = 0;
177 int64_t l = 0, z = tot;
178 memcpy(cnt, ec, 48);
179 p = block + 2 + *(const uint16_t*)block;
180 if (cy) {
181 move_backward(y)
182 for (a = 0; a != 6; ++a) cy[a] += cnt[a];
183 cy[*p&7] += y - z;
184 }
185 move_backward(x)
186 for (a = 0; a != 6; ++a) cx[a] += cnt[a];
187 cx[*p&7] += x - z;
188
189 #undef move_backward
190 }
191 }