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