1 /* Copyright 2016 Google Inc. All Rights Reserved.
2 Author: zip753@gmail.com (Ivan Nikulin)
3
4 Distributed under MIT license.
5 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
6 */
7
8 /* Backward reference visualization tool. Accepts file with backward references
9 as an input and produces PGM image with histogram of those references. */
10
11 #include <algorithm> /* min */
12 #include <cassert>
13 #include <cstring> /* memset */
14 #include <cmath> /* log, round */
15 #include <cstdio> /* fscanf, fprintf */
16 #include <cstdint>
17
18 #include <gflags/gflags.h>
19 using gflags::ParseCommandLineFlags;
20
21 #include "./read_dist.h"
22
23 DEFINE_int32(height, 1000, "Height of the resulting histogam.");
24 DEFINE_int32(width, 8000, "Width of the resulting histogam.");
25 DEFINE_int32(size, 1e8, "Size of the compressed file.");
26 DEFINE_int32(brotli_window, -1, "Size of brotli window in bits.");
27 DEFINE_uint64(min_distance, 0, "Minimum distance.");
28 DEFINE_uint64(max_distance, 1 << 30, "Maximum distance.");
29 DEFINE_bool(with_copies, false, "True if input contains copy length.");
30 DEFINE_bool(simple, false, "True if using only black and white pixels.");
31 DEFINE_bool(linear, false, "True if using linear distance mapping.");
32 DEFINE_uint64(skip, 0, "Number of bytes to skip.");
33
DistanceTransform(double x)34 inline double DistanceTransform(double x) {
35 static bool linear = FLAGS_linear;
36 if (linear) {
37 return x;
38 } else {
39 /* Using log^2 scale because log scale produces big white gap at the bottom
40 of image. */
41 return log(x) * log(x);
42 }
43 }
44
45 /* Mapping pixel density on arc function to increase contrast. */
DensityTransform(double x)46 inline double DensityTransform(double x) {
47 double z = 255 - x;
48 return sqrt(255 * 255 - z * z);
49 }
50
GetMaxDistance()51 inline int GetMaxDistance() {
52 return FLAGS_max_distance;
53 }
54
AdjustPosition(int * pos)55 void AdjustPosition(int* pos) {
56 static uint32_t offset = 0;
57 static int last = 0;
58 static uint32_t window_size = (1 << FLAGS_brotli_window);
59 assert(*pos >= 0 && *pos < window_size);
60 if (*pos < last) {
61 offset += window_size;
62 }
63 last = *pos;
64 *pos += offset;
65 }
66
BuildHistogram(FILE * fin,int ** histo)67 void BuildHistogram(FILE* fin, int** histo) {
68 int height = FLAGS_height;
69 int width = FLAGS_width;
70 int skip = FLAGS_skip;
71 size_t min_distance = FLAGS_min_distance;
72
73 printf("height = %d, width = %d\n", height, width);
74
75 for (int i = 0; i < height; i++) {
76 for (int j = 0; j < width; j++) {
77 histo[i][j] = 0;
78 }
79 }
80
81 int max_pos = FLAGS_size - skip;
82 double min_dist = min_distance > 0 ? DistanceTransform(min_distance) : 0;
83 double max_dist = DistanceTransform(GetMaxDistance()) - min_dist;
84 int copy, pos, distance, x, y;
85 double dist;
86 while (ReadBackwardReference(fin, ©, &pos, &distance)) {
87 if (pos == -1) continue; // In case when only insert is present.
88 if (distance < min_distance || distance >= GetMaxDistance()) continue;
89 if (FLAGS_brotli_window != -1) {
90 AdjustPosition(&pos);
91 }
92 if (pos >= skip && distance <= pos) {
93 pos -= skip;
94 if (pos >= max_pos) break;
95 dist = DistanceTransform(static_cast<double>(distance)) - min_dist;
96
97 x = std::min(static_cast<int>(round(dist / max_dist * height)),
98 height - 1);
99 y = 1ul * pos * width / max_pos;
100 if (!(y >= 0 && y < width)) {
101 printf("pos = %d, max_pos = %d, y = %d\n", pos, max_pos, y);
102 assert(y >= 0 && y < width);
103 }
104
105 if (FLAGS_with_copies) {
106 int right = 1ul * (pos + copy - 1) * width / max_pos;
107 if (right < 0) {
108 printf("pos = %d, distance = %d, copy = %d, y = %d, right = %d\n",
109 pos, distance, copy, y, right);
110 assert(right >= 0);
111 }
112 if (y == right) {
113 histo[x][y] += copy;
114 } else {
115 int pos2 = static_cast<int>(ceil(1.0 * (y + 1) * max_pos / width));
116 histo[x][y] += pos2 - pos;
117 for (int i = y + 1; i < right && i < width; ++i) {
118 histo[x][i] += max_pos / width; // Sometimes 1 more, but who cares.
119 }
120 // Make sure the match doesn't go beyond the image.
121 if (right < width) {
122 pos2 = static_cast<int>(ceil(1.0 * right * max_pos / width));
123 histo[x][right] += pos + copy - 1 - pos2 + 1;
124 }
125 }
126 } else {
127 histo[x][y]++;
128 }
129 }
130 }
131 }
132
ConvertToPixels(int ** histo,uint8_t ** pixel)133 void ConvertToPixels(int** histo, uint8_t** pixel) {
134 int height = FLAGS_height;
135 int width = FLAGS_width;
136
137 int maxs = 0;
138 for (int i = 0; i < height; i++) {
139 for (int j = 0; j < width; j++) {
140 if (maxs < histo[i][j]) maxs = histo[i][j];
141 }
142 }
143
144 bool simple = FLAGS_simple;
145 double max_histo = static_cast<double>(maxs);
146 for (int i = 0; i < height; i++) {
147 for (int j = 0; j < width; j++) {
148 if (simple) {
149 pixel[i][j] = histo[i][j] > 0 ? 0 : 255;
150 } else {
151 pixel[i][j] = static_cast<uint8_t>(
152 255 - DensityTransform(histo[i][j] / max_histo * 255));
153 }
154 }
155 }
156 }
157
DrawPixels(uint8_t ** pixel,FILE * fout)158 void DrawPixels(uint8_t** pixel, FILE* fout) {
159 int height = FLAGS_height;
160 int width = FLAGS_width;
161
162 fprintf(fout, "P5\n%d %d\n255\n", width, height);
163 for (int i = height - 1; i >= 0; i--) {
164 fwrite(pixel[i], 1, width, fout);
165 }
166 }
167
main(int argc,char * argv[])168 int main(int argc, char* argv[]) {
169 ParseCommandLineFlags(&argc, &argv, true);
170 if (argc != 3) {
171 printf("usage: draw_histogram.cc data output_file\n");
172 return 1;
173 }
174
175 int height = FLAGS_height;
176 int width = FLAGS_width;
177
178 FILE* fin = fopen(argv[1], "r");
179 FILE* fout = fopen(argv[2], "wb");
180
181 uint8_t** pixel = new uint8_t*[height];
182 int** histo = new int*[height];
183 for (int i = 0; i < height; i++) {
184 pixel[i] = new uint8_t[width];
185 histo[i] = new int[width];
186 }
187
188 BuildHistogram(fin, histo);
189 fclose(fin);
190
191 ConvertToPixels(histo, pixel);
192
193 DrawPixels(pixel, fout);
194 fclose(fout);
195
196 return 0;
197 }
198