158cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin/* Copyright 2016 Google Inc. All Rights Reserved. 2dd8fa3e8ddb970fd92550d6e833870a813e4b164Eugene Kliuchnikov Author: zip753@gmail.com (Ivan Nikulin) 358cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 458cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin Distributed under MIT license. 558cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin See file LICENSE for detail or copy at https://opensource.org/licenses/MIT 658cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin*/ 758cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 858cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin/* Backward reference visualization tool. Accepts file with backward references 958cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin as an input and produces PGM image with histogram of those references. */ 1058cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 1158cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin#include <algorithm> /* min */ 1258cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin#include <cassert> 1358cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin#include <cstring> /* memset */ 1458cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin#include <cmath> /* log, round */ 1558cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin#include <cstdio> /* fscanf, fprintf */ 1658cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin#include <cstdint> 1758cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 18dd8fa3e8ddb970fd92550d6e833870a813e4b164Eugene Kliuchnikov#include <gflags/gflags.h> 19dd8fa3e8ddb970fd92550d6e833870a813e4b164Eugene Kliuchnikovusing gflags::ParseCommandLineFlags; 20dd8fa3e8ddb970fd92550d6e833870a813e4b164Eugene Kliuchnikov 2158cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin#include "./read_dist.h" 2258cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 23dd8fa3e8ddb970fd92550d6e833870a813e4b164Eugene KliuchnikovDEFINE_int32(height, 1000, "Height of the resulting histogam."); 24dd8fa3e8ddb970fd92550d6e833870a813e4b164Eugene KliuchnikovDEFINE_int32(width, 8000, "Width of the resulting histogam."); 25dd8fa3e8ddb970fd92550d6e833870a813e4b164Eugene KliuchnikovDEFINE_int32(size, 1e8, "Size of the compressed file."); 26dd8fa3e8ddb970fd92550d6e833870a813e4b164Eugene KliuchnikovDEFINE_int32(brotli_window, -1, "Size of brotli window in bits."); 27dd8fa3e8ddb970fd92550d6e833870a813e4b164Eugene KliuchnikovDEFINE_uint64(min_distance, 0, "Minimum distance."); 28dd8fa3e8ddb970fd92550d6e833870a813e4b164Eugene KliuchnikovDEFINE_uint64(max_distance, 1 << 30, "Maximum distance."); 29dd8fa3e8ddb970fd92550d6e833870a813e4b164Eugene KliuchnikovDEFINE_bool(with_copies, false, "True if input contains copy length."); 30dd8fa3e8ddb970fd92550d6e833870a813e4b164Eugene KliuchnikovDEFINE_bool(simple, false, "True if using only black and white pixels."); 31dd8fa3e8ddb970fd92550d6e833870a813e4b164Eugene KliuchnikovDEFINE_bool(linear, false, "True if using linear distance mapping."); 32dd8fa3e8ddb970fd92550d6e833870a813e4b164Eugene KliuchnikovDEFINE_uint64(skip, 0, "Number of bytes to skip."); 3358cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 3458cecf1783c1a814f282f859609721fefebf74aaIvan Nikulininline double DistanceTransform(double x) { 3558cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin static bool linear = FLAGS_linear; 3658cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin if (linear) { 3758cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin return x; 3858cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } else { 3958cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin /* Using log^2 scale because log scale produces big white gap at the bottom 4058cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin of image. */ 4158cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin return log(x) * log(x); 4258cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 4358cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin} 4458cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 4558cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin/* Mapping pixel density on arc function to increase contrast. */ 4658cecf1783c1a814f282f859609721fefebf74aaIvan Nikulininline double DensityTransform(double x) { 4758cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin double z = 255 - x; 4858cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin return sqrt(255 * 255 - z * z); 4958cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin} 5058cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 5158cecf1783c1a814f282f859609721fefebf74aaIvan Nikulininline int GetMaxDistance() { 5258cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin return FLAGS_max_distance; 5358cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin} 5458cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 5558cecf1783c1a814f282f859609721fefebf74aaIvan Nikulinvoid AdjustPosition(int* pos) { 5658cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin static uint32_t offset = 0; 5758cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin static int last = 0; 5858cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin static uint32_t window_size = (1 << FLAGS_brotli_window); 5958cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin assert(*pos >= 0 && *pos < window_size); 6058cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin if (*pos < last) { 6158cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin offset += window_size; 6258cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 6358cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin last = *pos; 6458cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin *pos += offset; 6558cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin} 6658cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 670e52c59a07c62c537183a7848244037fe8172930Ivan Nikulinvoid BuildHistogram(FILE* fin, int** histo) { 6858cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin int height = FLAGS_height; 6958cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin int width = FLAGS_width; 7058cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin int skip = FLAGS_skip; 7158cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin size_t min_distance = FLAGS_min_distance; 7258cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 7358cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin printf("height = %d, width = %d\n", height, width); 7458cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 7558cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin for (int i = 0; i < height; i++) { 7658cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin for (int j = 0; j < width; j++) { 770e52c59a07c62c537183a7848244037fe8172930Ivan Nikulin histo[i][j] = 0; 7858cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 7958cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 8058cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 8158cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin int max_pos = FLAGS_size - skip; 8258cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin double min_dist = min_distance > 0 ? DistanceTransform(min_distance) : 0; 8358cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin double max_dist = DistanceTransform(GetMaxDistance()) - min_dist; 8458cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin int copy, pos, distance, x, y; 8558cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin double dist; 8658cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin while (ReadBackwardReference(fin, ©, &pos, &distance)) { 8758cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin if (pos == -1) continue; // In case when only insert is present. 8858cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin if (distance < min_distance || distance >= GetMaxDistance()) continue; 89dd8fa3e8ddb970fd92550d6e833870a813e4b164Eugene Kliuchnikov if (FLAGS_brotli_window != -1) { 9058cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin AdjustPosition(&pos); 9158cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 9258cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin if (pos >= skip && distance <= pos) { 9358cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin pos -= skip; 9458cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin if (pos >= max_pos) break; 9558cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin dist = DistanceTransform(static_cast<double>(distance)) - min_dist; 9658cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 9758cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin x = std::min(static_cast<int>(round(dist / max_dist * height)), 9858cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin height - 1); 9958cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin y = 1ul * pos * width / max_pos; 10058cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin if (!(y >= 0 && y < width)) { 10158cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin printf("pos = %d, max_pos = %d, y = %d\n", pos, max_pos, y); 10258cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin assert(y >= 0 && y < width); 10358cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 10458cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 10558cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin if (FLAGS_with_copies) { 10658cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin int right = 1ul * (pos + copy - 1) * width / max_pos; 10758cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin if (right < 0) { 10858cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin printf("pos = %d, distance = %d, copy = %d, y = %d, right = %d\n", 10958cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin pos, distance, copy, y, right); 11058cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin assert(right >= 0); 11158cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 11258cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin if (y == right) { 1130e52c59a07c62c537183a7848244037fe8172930Ivan Nikulin histo[x][y] += copy; 11458cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } else { 11558cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin int pos2 = static_cast<int>(ceil(1.0 * (y + 1) * max_pos / width)); 1160e52c59a07c62c537183a7848244037fe8172930Ivan Nikulin histo[x][y] += pos2 - pos; 11758cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin for (int i = y + 1; i < right && i < width; ++i) { 1180e52c59a07c62c537183a7848244037fe8172930Ivan Nikulin histo[x][i] += max_pos / width; // Sometimes 1 more, but who cares. 11958cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 12058cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin // Make sure the match doesn't go beyond the image. 12158cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin if (right < width) { 12258cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin pos2 = static_cast<int>(ceil(1.0 * right * max_pos / width)); 1230e52c59a07c62c537183a7848244037fe8172930Ivan Nikulin histo[x][right] += pos + copy - 1 - pos2 + 1; 12458cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 12558cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 12658cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } else { 1270e52c59a07c62c537183a7848244037fe8172930Ivan Nikulin histo[x][y]++; 12858cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 12958cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 13058cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 13158cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin} 13258cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 1330e52c59a07c62c537183a7848244037fe8172930Ivan Nikulinvoid ConvertToPixels(int** histo, uint8_t** pixel) { 13458cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin int height = FLAGS_height; 13558cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin int width = FLAGS_width; 13658cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 13758cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin int maxs = 0; 13858cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin for (int i = 0; i < height; i++) { 13958cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin for (int j = 0; j < width; j++) { 1400e52c59a07c62c537183a7848244037fe8172930Ivan Nikulin if (maxs < histo[i][j]) maxs = histo[i][j]; 14158cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 14258cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 14358cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 14458cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin bool simple = FLAGS_simple; 1450e52c59a07c62c537183a7848244037fe8172930Ivan Nikulin double max_histo = static_cast<double>(maxs); 14658cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin for (int i = 0; i < height; i++) { 14758cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin for (int j = 0; j < width; j++) { 14858cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin if (simple) { 1490e52c59a07c62c537183a7848244037fe8172930Ivan Nikulin pixel[i][j] = histo[i][j] > 0 ? 0 : 255; 15058cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } else { 15158cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin pixel[i][j] = static_cast<uint8_t>( 1520e52c59a07c62c537183a7848244037fe8172930Ivan Nikulin 255 - DensityTransform(histo[i][j] / max_histo * 255)); 15358cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 15458cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 15558cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 15658cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin} 15758cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 15858cecf1783c1a814f282f859609721fefebf74aaIvan Nikulinvoid DrawPixels(uint8_t** pixel, FILE* fout) { 15958cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin int height = FLAGS_height; 16058cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin int width = FLAGS_width; 16158cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 16258cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin fprintf(fout, "P5\n%d %d\n255\n", width, height); 16358cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin for (int i = height - 1; i >= 0; i--) { 16458cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin fwrite(pixel[i], 1, width, fout); 16558cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 16658cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin} 16758cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 16858cecf1783c1a814f282f859609721fefebf74aaIvan Nikulinint main(int argc, char* argv[]) { 169dd8fa3e8ddb970fd92550d6e833870a813e4b164Eugene Kliuchnikov ParseCommandLineFlags(&argc, &argv, true); 170dd8fa3e8ddb970fd92550d6e833870a813e4b164Eugene Kliuchnikov if (argc != 3) { 171dd8fa3e8ddb970fd92550d6e833870a813e4b164Eugene Kliuchnikov printf("usage: draw_histogram.cc data output_file\n"); 17258cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin return 1; 17358cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 17458cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 17558cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin int height = FLAGS_height; 17658cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin int width = FLAGS_width; 17758cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 17858cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin FILE* fin = fopen(argv[1], "r"); 179dd8fa3e8ddb970fd92550d6e833870a813e4b164Eugene Kliuchnikov FILE* fout = fopen(argv[2], "wb"); 18058cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 18158cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin uint8_t** pixel = new uint8_t*[height]; 1820e52c59a07c62c537183a7848244037fe8172930Ivan Nikulin int** histo = new int*[height]; 18358cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin for (int i = 0; i < height; i++) { 18458cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin pixel[i] = new uint8_t[width]; 1850e52c59a07c62c537183a7848244037fe8172930Ivan Nikulin histo[i] = new int[width]; 18658cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin } 18758cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 1880e52c59a07c62c537183a7848244037fe8172930Ivan Nikulin BuildHistogram(fin, histo); 18958cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin fclose(fin); 19058cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 1910e52c59a07c62c537183a7848244037fe8172930Ivan Nikulin ConvertToPixels(histo, pixel); 19258cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 19358cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin DrawPixels(pixel, fout); 19458cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin fclose(fout); 19558cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin 19658cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin return 0; 19758cecf1783c1a814f282f859609721fefebf74aaIvan Nikulin} 198