Buckets:
agent-collaborations/hutter-prize-67 / decoder-bundle-minimization /work /paq8px-src /src /ResidualMap.cpp
| | |
| ResidualMap::ResidualMap(const Shared* const sh, const int numContexts, const int histogramsPerContext, const int scale) : | |
| shared(sh), | |
| scale(scale), | |
| numContexts(numContexts), | |
| histogramsPerContext(histogramsPerContext), | |
| currentContextIndex(0), | |
| predictions(numContexts), | |
| bases(numContexts), | |
| sums(BINS* numContexts* histogramsPerContext) { | |
| dt = DivisionTable::getDT(); | |
| } | |
| void ResidualMap::setscale(const int scale) { | |
| this->scale = scale; | |
| } | |
| void ResidualMap::set(const short prediction, const uint32_t histogram_id) { | |
| assert(histogram_id < histogramsPerContext); | |
| assert(currentContextIndex < numContexts); | |
| predictions[currentContextIndex] = prediction; | |
| bases[currentContextIndex] = (currentContextIndex * histogramsPerContext + histogram_id) * BINS; | |
| currentContextIndex++; | |
| } | |
| void ResidualMap::skip() { | |
| assert(currentContextIndex < numContexts); | |
| bases[currentContextIndex] = UINT32_MAX; | |
| currentContextIndex++; | |
| } | |
| void ResidualMap::mix(Mixer& m) { | |
| INJECT_SHARED_bpos | |
| INJECT_SHARED_c0 | |
| if (bpos == 7) | |
| shared->GetUpdateBroadcaster()->subscribe(this); | |
| assert(currentContextIndex == numContexts); | |
| for (size_t i = 0; i < currentContextIndex; i++) { | |
| const uint32_t base = bases[i]; | |
| if (base == UINT32_MAX) { // skipped context | |
| m.add(0); | |
| m.add(0); | |
| continue; | |
| } | |
| const uint16_t* s = &sums[base]; | |
| const uint8_t c1 = c0 << (8 - bpos); | |
| const int range = 1 << (7 - bpos); // 128 down to 1 | |
| // n0: bins [offset, offset+range) mod 256 | |
| // n1: bins [mid, mid+range) mod 256 | |
| // s[k] = count[0]+...+count[k], k=0..BINS-1, s[BINS-1]=total. | |
| // Circular range [a, a+len): no wrap → s[a+len-1]-s[a-1]; wrap → s[BINS-1]-s[a-1]+s[a+len-BINS-1]. | |
| // boundary cases: | |
| // a==0 → s[a-1] treated as 0. | |
| // offset+range == BINS is the exact-fit case: s[BINS-1] is the last valid entry, no wrap needed. | |
| const int bin0_offset = (192 + c1 - predictions[i]) & 255; | |
| const int bin1_offset = (bin0_offset + range) & 255; | |
| // n0: observation count in the "next bit = 0" residual window (lower half) | |
| // n1: observation count in the "next bit = 1" residual window (upper half) | |
| uint64_t n0, n1; | |
| // n0 | |
| if (bin0_offset + range <= BINS) | |
| n0 = s[bin0_offset + range - 1] - (bin0_offset == 0 ? 0 : s[bin0_offset - 1]); | |
| else | |
| n0 = s[BINS - 1] - s[bin0_offset - 1] + s[bin0_offset + range - BINS - 1]; | |
| // n1 | |
| if (bin1_offset + range <= BINS) | |
| n1 = s[bin1_offset + range - 1] - (bin1_offset == 0 ? 0 : s[bin1_offset - 1]); | |
| else | |
| n1 = s[BINS - 1] - s[bin1_offset - 1] + s[bin1_offset + range - BINS - 1]; | |
| // we need p1 = 4096*(n1+1)/(n0+n1+2) | |
| // to avoid the division: | |
| const uint64_t raw_sum = n0 + n1; // [0..131070] where 131070 = two times UINT16_MAX | |
| // to use dt, we need sum to be [0..1023] → we need to shift raw_sum by how much? | |
| // 131070 >> 7 = 1023 | |
| // 65535 >> 6 = 1023 | |
| // 32767 >> 5 = 1023 | |
| // ... | |
| // 4095 >> 2 = 1023 | |
| // 2047 >> 1 = 1023 | |
| // 1023 >> 0 = 1023 | |
| // the shift needed is the number of bits in raw_sum - 10 | |
| // the number of bits in raw_sum is 32 - clz(raw_sum) | |
| // clz is undefined for 0, but raw_sum==0 → shift=0 anyway, | |
| // so we OR with 1 to make clz safe; it doesn't affect the result when raw_sum>0. | |
| const int shift_raw = 32 - 10 - clz((uint32_t)(raw_sum | 1)); | |
| const int shift = shift_raw & ~(shift_raw >> 31); // max(shift_raw, 0) without branch | |
| const size_t sum_small = raw_sum >> shift; // [0..1023] | |
| n1 = (n1 >> shift) + 1; | |
| const int p1 = (int)(((n1 << 12) * (uint64_t)dt[sum_small]) >> 30); //4096 * (n1+1) / (n0+n1+2) | |
| m.add((stretch(p1) * scale) >> 8); | |
| m.add(((p1 - 2048) * scale) >> 9); | |
| } | |
| } | |
| void ResidualMap::update() { | |
| assert(shared->State.bitPosition == 0); | |
| assert(currentContextIndex == numContexts); | |
| while (currentContextIndex > 0) { | |
| currentContextIndex--; | |
| const uint32_t base = bases[currentContextIndex]; | |
| if (base == UINT32_MAX) | |
| continue; | |
| INJECT_SHARED_c1 | |
| const int bin = (192 + c1 - predictions[currentContextIndex]) & 255; // moving the center to bin #192 gives better cache locality on read and on updates | |
| // Increment all prefix entries after bin: sums[bin .. BINS-1] += 1. | |
| uint16_t* s = &sums[base]; | |
| for (int k = bin; k < BINS; k++) | |
| s[k]++; | |
| // Aging: when the total reaches UINT16_MAX halve all prefix entries. | |
| // A bin's count is s[k]-s[k-1] (s[-1] treated as 0); total is s[BINS-1]. | |
| if (s[BINS - 1] == UINT16_MAX) { | |
| for (int k = 0; k < BINS; k++) | |
| s[k] >>= 1; | |
| } | |
| } | |
| } | |
| void ResidualMap::print() { | |
| for (size_t i = 0; i < numContexts; i++) { | |
| for (size_t j = 0; j < histogramsPerContext; j++) { | |
| const uint16_t* s = &sums[(i * histogramsPerContext + j) * BINS]; | |
| printf("%zu\t%zu", i, j); | |
| for (int k = 0; k < BINS; k++) | |
| printf("\t%d", k == 0 ? s[0] : s[k] - s[k - 1]); | |
| printf("\n"); | |
| } | |
| } | |
| } | |
Xet Storage Details
- Size:
- 5.07 kB
- Xet hash:
- feaf513cf9bf086881272663d7b938fa66f4a50ff9753836e3a055a966ce3f2e
·
Xet efficiently stores files, intelligently splitting them into unique chunks and accelerating uploads and downloads. More info.