rescale_freq.cpp

template<int scale_bits> void rescale_freq16(uint16(&freq)[0x100]) {
	const int total_freq = 1 << scale_bits;

	int total = 0;
	for (int i = 0; i < 0x100; i++) {
		total += freq[i];
	}

	uint64 div = (1ULL << 31) / total;

	uint32 scaled[0x100];
	for (int i = 0; i < 0x100; i++) {
		//scaled[i] = (uint32(freq[i]) << scale_bits) / total;
		scaled[i] = (uint64(freq[i]) * div) >> (31 - scale_bits);
	}

	for (int i = 0; i < 0x100; i++) {
		if (scaled[i] == 0 && freq[i] > 0) {
			int t = 0;
			for (int j = 1; j < 0x100; j++) {
				if (scaled[j] > scaled[t]) {
					t = j;
				}
			}

			--scaled[t];
			++scaled[i];
		}
	}

	for (int i = 0; i < 0x100; i++) {
		ASSERT(!(scaled[i] & ~0xFFFF));
		scaled[i] = (scaled[i] << 8) + i;
	}

	total = 0;
	for (int i = 0; i < 0x100; i++) {
		total += scaled[i] >> 8;
	}

	for (int i = 1; i < 0x100; i++) {
		int j = i;
		while (j > 0 && scaled[j] > scaled[j - 1]) {
			Swap(scaled[j], scaled[j - 1]);
			j--;
		}
	}

	int num_valid = 0;
	while (num_valid < 0x100 && (scaled[num_valid] >> 8)) { ++num_valid; }

	ASSERT(total <= total_freq);

	if (total < total_freq) {
		const int step = ((total_freq >> 1) + (total_freq >> 3) + 3);
		const int total_freq_mask = (1 << scale_bits) - 1;

		byte sym_table[total_freq];
		int sym_table_size = 0;

		for (int i = 0; i < 0x100; i++) {
			for (int c = 0; c < (scaled[i] >> 8); c++) {
				sym_table[sym_table_size++] = i;
			}
		}

		int pos = 0;
		while (total < total_freq) {
			int i = sym_table[pos];
			scaled[i] += 1 << 8;
			++total;

			do {
				pos = (pos + step) & total_freq_mask;
			}
			while (pos >= sym_table_size);
		}
	}

	for (int i = 0; i < 0x100; i++) {
		ASSERT((freq[scaled[i] & 0xFF] == 0) == ((scaled[i] >> 8) == 0));
		freq[scaled[i] & 0xFF] = scaled[i] >> 8;
	}

	total = 0;
	for (int i = 0; i < 0x100; i++) {
		total += freq[i];
	}

	ASSERT(total == (1 << scale_bits));
}