1 // This file is part of the brlaser printer driver.
2 //
3 // Copyright 2013 Peter De Wachter
4 //
5 // brlaser is free software: you can redistribute it and/or modify
6 // it under the terms of the GNU General Public License as published by
7 // the Free Software Foundation, either version 2 of the License, or
8 // (at your option) any later version.
9 //
10 // brlaser is distributed in the hope that it will be useful,
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 // GNU General Public License for more details.
14 //
15 // You should have received a copy of the GNU General Public License
16 // along with brlaser. If not, see <http://www.gnu.org/licenses/>.
17
18 #include "line.h"
19 #include <assert.h>
20 #include <algorithm>
21 using std::vector;
22
23 namespace {
24
write_overflow(int value,vector<uint8_t> * out)25 void write_overflow(int value, vector<uint8_t> *out) {
26 if (value >= 0) {
27 if (value < 255) {
28 out->push_back(value);
29 } else {
30 out->insert(out->end(), value / 255, 255);
31 out->push_back(value % 255);
32 }
33 }
34 }
35
36 template <typename Iterator>
write_substitute(int offset,Iterator first,Iterator last,vector<uint8_t> * out)37 void write_substitute(int offset,
38 Iterator first,
39 Iterator last,
40 vector<uint8_t> *out) {
41 assert(offset >= 0);
42 assert(offset < 10000);
43 assert(first != last);
44
45 const int offset_max = 15;
46 const int count_max = 7;
47 int count = std::distance(first, last) - 1;
48
49 int offset_low = std::min(offset, offset_max);
50 int count_low = std::min(count, count_max);
51 out->push_back((offset_low << 3) | count_low);
52 write_overflow(offset - offset_max, out);
53 write_overflow(count - count_max, out);
54 out->insert(out->end(), first, last);
55 }
56
write_repeat(int offset,int count,int value,vector<uint8_t> * out)57 void write_repeat(int offset, int count, int value, vector<uint8_t> *out) {
58 assert(offset >= 0);
59 assert(offset < 10000);
60 assert(count >= 2);
61 assert(count < 10000);
62
63 const int offset_max = 3;
64 const int count_max = 31;
65 count -= 2;
66
67 int offset_low = std::min(offset, offset_max);
68 int count_low = std::min(count, count_max);
69 out->push_back(128 | (offset_low << 5) | count_low);
70 write_overflow(offset - offset_max, out);
71 write_overflow(count - count_max, out);
72 out->push_back(value);
73 }
74
75
all_zeros(const vector<uint8_t> & buf)76 bool all_zeros(const vector<uint8_t> &buf) {
77 return std::none_of(buf.begin(), buf.end(), [](uint8_t b) { return b; });
78 }
79
80 template <typename Iterator1, typename Iterator2>
skip_to_next_mismatch(Iterator1 * first1,Iterator1 last1,Iterator2 * first2)81 int skip_to_next_mismatch(Iterator1 *first1,
82 Iterator1 last1,
83 Iterator2 *first2) {
84 auto mismatch_it = std::mismatch(*first1, last1, *first2);
85 int skipped = std::distance(*first1, mismatch_it.first);
86 *first1 = mismatch_it.first;
87 *first2 = mismatch_it.second;
88 return skipped;
89 }
90
91 template <typename Iterator>
repeat_length(Iterator first,Iterator last)92 int repeat_length(Iterator first, Iterator last) {
93 if (first != last) {
94 auto k = *first;
95 auto mismatch = std::find_if(std::next(first), last,
96 [=](decltype(k) x) { return x != k; });
97 return std::distance(first, mismatch);
98 }
99 return 0;
100 }
101
102 template <typename Iterator1, typename Iterator2>
substitute_length(Iterator1 first1,Iterator1 last1,Iterator2 first2)103 int substitute_length(Iterator1 first1, Iterator1 last1, Iterator2 first2) {
104 if (first1 != last1) {
105 Iterator1 it1 = first1;
106 Iterator2 it2 = first2;
107 Iterator1 next1 = std::next(first1);
108 Iterator2 next2 = std::next(first2);
109 Iterator1 prev1 = first1;
110 while (next1 != last1) {
111 if ((*it1 == *it2 && *next1 == *next2)) {
112 return std::distance(first1, it1);
113 }
114 if (*it1 == *next1 && *it1 == *prev1) {
115 return std::distance(first1, prev1);
116 }
117 prev1 = it1;
118 it1 = next1; it2 = next2;
119 ++next1; ++next2;
120 }
121 }
122 return std::distance(first1, last1);
123 }
124
reserve_size(const vector<uint8_t> & line)125 size_t reserve_size(const vector<uint8_t> &line) {
126 // Big enough to store the line uncompressed together with an Substitute
127 // command with many overflow bytes.
128 return line.size() + 16;
129 }
130
131 } // namespace
132
encode_line(const vector<uint8_t> & line,const vector<uint8_t> & reference)133 vector<uint8_t> encode_line(const vector<uint8_t> &line,
134 const vector<uint8_t> &reference) {
135 assert(line.size() == reference.size());
136 if (all_zeros(line)) {
137 return vector<uint8_t>(1, 0xFF);
138 }
139
140 vector<uint8_t> output;
141 output.reserve(reserve_size(line));
142 output.push_back(0); // first byte is the edit count
143
144 const uint8_t max_edits = 254;
145 int num_edits = 0;
146
147 auto line_it = line.begin();
148 auto line_end_it =
149 std::mismatch(line.rbegin(), line.rend(), reference.rbegin()).first.base();
150 auto ref_it = reference.begin();
151 while (1) {
152 int offset = skip_to_next_mismatch(&line_it, line_end_it, &ref_it);
153 if (line_it == line_end_it) {
154 // No more differences, we're done.
155 break;
156 }
157
158 if (++num_edits == max_edits) {
159 // We've run out of edits. Just output the rest of the line in a big
160 // substitute command.
161 write_substitute(offset, line_it, line_end_it, &output);
162 break;
163 }
164
165 int s = substitute_length(line_it, line_end_it, ref_it);
166 if (s > 0) {
167 write_substitute(offset, line_it, std::next(line_it, s), &output);
168 line_it += s;
169 ref_it += s;
170 } else {
171 int r = repeat_length(line_it, line_end_it);
172 assert(r >= 2);
173 write_repeat(offset, r, *line_it, &output);
174 line_it += r;
175 ref_it += r;
176 }
177 }
178
179 assert(num_edits <= max_edits);
180 output[0] = num_edits;
181 return output;
182 }
183
encode_line(const vector<uint8_t> & line)184 vector<uint8_t> encode_line(const vector<uint8_t> &line) {
185 if (all_zeros(line)) {
186 return vector<uint8_t>(1, 0xFF);
187 }
188 vector<uint8_t> buf;
189 buf.reserve(reserve_size(line));
190 buf.push_back(1);
191 write_substitute(0, line.begin(), line.end(), &buf);
192 return buf;
193 }
194