15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2006-2009 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Remember a subset of a sequence of values, using a modest amount of memory 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)/*** 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Design: 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Accumulate in powers of three, using 3-way median to collapse entries. 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) At any given time, there is one most-dense (highest power of 3) range of 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) entries and a series of less-dense ranges that hold 0..2 entries each. There 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) is a bounded-size storage array of S cells for all the entries. 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) The overflow detect is set up so that a new higher power of 3, K+1, is 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) triggered precisely when range K has 3n entries and all ranges < K have 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) zero entries. 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) In general, think of the range sizes as a multi-digit base 3 number, except 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) the highest digit may exceed 2: 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3**6 3**5 3**4 3**3 3**2 3**1 3**0 K=2 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0 0 0 0 3n-1 2 2 unused:1 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) There are a total of 3n-1 + 2 + 2 entries in use. Assume a size limit S at 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) one more than that, and we add a new 3**0 entry and "carry" by performing 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) medians on any group of 3 elements: 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3**6 3**5 3**4 3**3 3**2 3**1 3**0 K=2 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0 0 0 0 3n-1 2 3 unused:0 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0 0 0 0 3n-1 3 0 carry unused:2 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0 0 0 0 3n 0 0 carry unused:4 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) To accumulate 2 entries at all levels < K and 3 just before the first carry at 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) level 0, we need 2*K + 1 unused cells after doing all carries, or five cells 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) in this case. Since we only have 4 cells in the example above, we need to 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) make room by starting a new power of three: 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 3**6 3**5 3**4 3**3 3**2 3**1 3**0 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0 0 0 0 3n 0 0 K=2 unused:4 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 0 0 0 n 0 0 0 K=3 unused:2n+4 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) In the code below, we don't worry about overflow from the topmost place. 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)***/ 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "encodings/compact_lang_det/subsetsequence.h" 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include <stdio.h> 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "encodings/compact_lang_det/win/cld_logging.h" 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void DumpInts(const char* label, const int* v, int n) { 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) printf("%s ", label); 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < n; ++i) { 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) printf("%d ", v[i]); 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) printf("\n"); 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void DumpUint8s(const char* label, const uint8* v, int n) { 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) printf("%s ", label); 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < n; ++i) { 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) printf("%d ", v[i]); 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) printf("\n"); 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Return median of seq_[sub] .. seq_[sub+2], favoring middle element 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)uint8 SubsetSequence::Median3(int sub) { 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (seq_[sub] == seq_[sub + 1]) { 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return seq_[sub]; 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (seq_[sub] == seq_[sub + 2]) { 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return seq_[sub]; 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return seq_[sub + 1]; 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SubsetSequence::Init() { 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // printf("Init\n"); 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) k_ = 0; 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) count_[0] = 0; 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next_e_ = 0; 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) seq_[0] = 0; // Default value if no calls to Add 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Want largest <= kMaxSeq_ that allows reserve and makes count_[k_] = 0 mod 3 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int reserve = (2 * k_ + 1); 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) level_limit_e_ = kMaxSeq_ - reserve; 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) level_limit_e_ = (level_limit_e_ / 3) * 3; // Round down to multiple of 3 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) limit_e_ = level_limit_e_; 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Compress level k by 3x, creating level k+1 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SubsetSequence::NewLevel() { 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // printf("NewLevel 3 ** %d\n", k_ + 1); 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) //DumpUint8s("count[k]", count_, k_ + 1); 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) //DumpUint8s("seq[next]", seq_, next_e_); 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Incoming level must be an exact multiple of three in size 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK((count_[k_] % 3) == 0); 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int k_size = count_[k_]; 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int new_size = k_size / 3; 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Compress down by 3x, via median 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int j = 0; j < new_size; ++j) { 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) seq_[j] = Median3(j * 3); 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Update counts 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) count_[k_] = 0; 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Else Overflow -- just continue with 3x dense Level K 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (k_ < (kMaxLevel_ - 1)) {++k_;} 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) count_[k_] = new_size; 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Update limits 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next_e_ = new_size; 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) limit_e_ = next_e_ + 3; 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Want largest <= kMaxSeq_ that allows reserve and makes count_[k_] = 0 mod 3 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int reserve = (2 * k_ + 1); 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) level_limit_e_ = kMaxSeq_ - reserve; 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) level_limit_e_ = (level_limit_e_ / 3) * 3; // Round down to multiple of 3 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) //DumpUint8s("after: count[k]", count_, k_ + 1); 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) //DumpUint8s("after: seq[next]", seq_, next_e_); 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SubsetSequence::DoCarries() { 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(count_[k_] > 3); // We depend on count_[k_] being > 3 to stop while 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Make room by carrying 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) //DumpUint8s("DoCarries count[k]", count_, k_ + 1); 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) //DumpUint8s("DoCarries seq[next]", seq_, next_e_); 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i = 0; 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (count_[i] == 3) { 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next_e_ -= 3; 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) seq_[next_e_] = Median3(next_e_); 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++next_e_; 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) count_[i] = 0; 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++count_[i + 1]; 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++i; 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) limit_e_ = next_e_ + 3; 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) //DumpUint8s("after: DoCarries count[k]", count_, k_ + 1); 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) //DumpUint8s("after: DoCarries seq[next]", seq_, next_e_); 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // If we just fully carried into level K, 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Make sure there is now enough room, else start level K + 1 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (i >= k_) { 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) CHECK(count_[k_] == next_e_); 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (next_e_ >= level_limit_e_) { 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) NewLevel(); 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SubsetSequence::Add(uint8 e) { 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Add an entry then carry as needed 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) seq_[next_e_] = e; 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++next_e_; 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++count_[0]; 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (next_e_ >= limit_e_) { 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) DoCarries(); 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Collapse tail end by simple median across disparate-weight values, 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// dropping or duplicating last value if need be. 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This routine is idempotent. 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SubsetSequence::Flush() { 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // printf("Flush %d\n", count_[k_]); 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int start_tail = count_[k_]; 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int size_tail = next_e_ - start_tail; 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((size_tail % 3) == 2) { 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) seq_[next_e_] = seq_[next_e_ - 1]; // Duplicate last value 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++size_tail; 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Compress tail down by 3x, via median 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int new_size = size_tail / 3; // May delete last value 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int j = 0; j < new_size; ++j) { 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) seq_[start_tail + j] = Median3(start_tail + j * 3); 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next_e_ = start_tail + new_size; 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) count_[k_] = next_e_; 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Extract representative pattern of exactly N values into dst[0..n-1] 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// This routine may be called multiple times, but it may downsample as a 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// side effect, causing subsequent calls with larger N to get poor answers. 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void SubsetSequence::Extract(int to_n, uint8* dst) { 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Collapse partial-carries in tail 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Flush(); 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Just use Bresenham to resample 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int from_n = next_e_; 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (to_n >= from_n) { 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Up-sample from_n => to_n 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int err = to_n - 1; // bias toward no overshoot 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int j = 0; 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < to_n; ++i) { 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dst[i] = seq_[j]; 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err -= from_n; 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (err < 0) { 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++j; 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err += to_n; 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Get to the point that the number of samples is <= 3 * to_n 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) while (next_e_ > (to_n * 3)) { 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Compress down by 3x, via median 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // printf("Extract, median %d / 3\n", next_e_); 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if ((next_e_ % 3) == 2) { 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) seq_[next_e_] = seq_[next_e_ - 1]; // Duplicate last value 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++next_e_; 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int new_size = next_e_ / 3; // May delete last value 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int j = 0; j < new_size; ++j) { 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) seq_[j] = Median3(j * 3); 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) next_e_ = new_size; 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) count_[k_] = next_e_; 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) from_n = next_e_; 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (to_n == from_n) { 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Copy verbatim 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < to_n; ++i) { 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dst[i] = seq_[i]; 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) return; 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Down-sample from_n => to_n, using medians 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int err = 0; // Bias to immediate median sample 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int j = 0; 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (int i = 0; i < from_n; ++i) { 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err -= to_n; 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (err < 0) { 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) if (i <= (next_e_ - 2)) { 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dst[j] = Median3(i); 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } else { 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) dst[j] = seq_[i]; 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++j; 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) err += from_n; 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 260