-static double cache[NUM_SYMS + 1][prob_scale + 1];
-static double log2cache[prob_scale + 1];
-static int64_t cachefill = 0;
-
-double find_optimal_cost(const uint32_t *cum_freqs, int sym_to, int available_slots)
-{
- assert(sym_to >= 0);
-
- while (sym_to > 0 && cum_freqs[sym_to] == cum_freqs[sym_to - 1]) { --sym_to; }
- if (cache[sym_to][available_slots] >= 0.0) {
- //printf("CACHE: %d,%d\n", sym_to, available_slots);
- return cache[sym_to][available_slots];
- }
- if (sym_to == 0) {
- return 0.0;
- }
- if (sym_to == 1) {
- return cum_freqs[0] * log2cache[available_slots];
- }
- if (available_slots == 1) {
- return cum_freqs[0] * log2cache[1] + find_optimal_cost(cum_freqs, sym_to - 1, 0);
- }
-
-// printf("UNCACHE: %d,%d\n", sym_to, available_slots);
-#if 0
- // ok, test all possible options for the last symbol (TODO: save the choice)
- double best_so_far = HUGE_VAL;
- //for (int i = num_syms - 1; i < available_slots; ++i) {
- double f = freqs[sym_to - 1];
- for (int i = available_slots; i --> 0; ) {
- double cost1 = f * log2cache[available_slots - i];
- double cost2 = find_optimal_cost(freqs, sym_to - 1, i);
-
- if (sym_to == 3 && available_slots == 838) {
- printf("%d %f\n", i, cost1 + cost2);
- } else
- if (cost1 + cost2 > best_so_far) {
- break;
- }
- best_so_far = cost1 + cost2;
- }
-#elif 1
- // Minimize the number of total bits spent as a function of how many slots
- // we assign to this symbol.
- //
- // The cost function is convex (I don't know how to prove it, but it makes
- // intuitively a lot of sense). Find a reasonable guess and see what way
- // we should search, then iterate until we either hit the end or we start
- // increasing again.
- double f = cum_freqs[sym_to - 1] - cum_freqs[sym_to - 2];
- double start = lrint(available_slots * f / cum_freqs[sym_to - 1]);
-
- int x1 = std::max<int>(floor(start), 1);
- int x2 = x1 + 1;
-
- double f1 = f * log2cache[x1] + find_optimal_cost(cum_freqs, sym_to - 1, available_slots - x1);
- double f2 = f * log2cache[x2] + find_optimal_cost(cum_freqs, sym_to - 1, available_slots - x2);
-
- int x, direction; // -1 or +1
- double best_so_far = std::min(f1, f2);
- if (isinf(f1) && isinf(f2)) {
- // The cost isn't infinite due to the first term, so we need to go downwards
- // to give the second term more room to breathe.
- x = x1;
- direction = -1;
- } else if (f1 < f2) {
- x = x1;
- direction = -1;
- } else {
- x = x2;
- direction = 1;
- }
-
- //printf("[%d,%d] freq=%ld cumfreq=%d From %d and %d, chose %d [%f] and direction=%d\n",
- // sym_to, available_slots, freqs[sym_to - 1], cum_freqs[sym_to - 1], x1, x2, x, best_so_far, direction);
-
- while ((x + direction) > 0 && (x + direction) <= available_slots) {
- x += direction;
- double fn = f * log2cache[x] + find_optimal_cost(cum_freqs, sym_to - 1, available_slots - x);
- // printf("[%d,%d] %d is %f\n", sym_to, available_slots, x, fn);
- if (fn > best_so_far) {
- break;
- }
- best_so_far = fn;
- }
-#endif
- if (++cachefill % 131072 == 0) {
- // printf("%d,%d = %f (cachefill = %.2f%%)\n", sym_to, available_slots, best_so_far,
- // 100.0 * (cachefill / double((NUM_SYMS + 1) * (prob_scale + 1))));
- }
- assert(best_so_far >= 0.0);
- assert(cache[sym_to][available_slots] < 0.0);
- cache[sym_to][available_slots] = best_so_far;
- return best_so_far;
-}
-
-double find_optimal_cost(const uint32_t *cum_freqs, const uint64_t *freqs)
-{
- for (int j = 0; j <= NUM_SYMS; ++j) {
- for (unsigned k = 0; k <= prob_scale; ++k) {
- cache[j][k] = -1.0;
- }
- }
- for (unsigned k = 0; k <= prob_scale; ++k) {
- log2cache[k] = -log2(k * (1.0 / prob_scale));
- //printf("log2cache[%d] = %f\n", k, log2cache[k]);
- }
- cachefill = 0;
- double ret = find_optimal_cost(cum_freqs, NUM_SYMS, prob_scale);
- printf("Used %ld function invocations\n", cachefill);
- return ret;
-}
-