| 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 |
} |