8 fn new() -> Self { Self { seed: 0x1234 } }
9 fn next(&mut self) -> u8 {
10 if (self.seed & 0x8000) != 0 {
11 self.seed = ((self.seed & 0x7FFF) * 2) ^ 0x1B2B;
19 #[derive(Default,Clone,Copy,PartialEq,Debug)]
35 fn new(centroid: Pixel) -> Self {
52 fn add_pixel(&mut self, entry: &Entry) {
53 self.sum_r += u64::from(entry.pix.r) * entry.count;
54 self.sum_g += u64::from(entry.pix.g) * entry.count;
55 self.sum_b += u64::from(entry.pix.b) * entry.count;
56 self.count += entry.count;
58 fn add_dist(&mut self, entry: &Entry) {
59 self.dist += u64::from(self.centroid.dist(entry.pix)) * entry.count;
61 fn calc_centroid(&mut self) {
63 self.centroid.r = ((self.sum_r + self.count / 2) / self.count) as u8;
64 self.centroid.g = ((self.sum_g + self.count / 2) / self.count) as u8;
65 self.centroid.b = ((self.sum_b + self.count / 2) / self.count) as u8;
68 fn calc_dist(&mut self) {
73 clusters: Vec<Cluster>,
78 pub fn new(initial_pal: &[[u8; 3]; 256]) -> Self {
79 let mut clusters = Vec::with_capacity(256);
81 let pix = Pixel { r: initial_pal[i][0], g: initial_pal[i][1], b: initial_pal[i][2] };
82 let cluster = Cluster::new(pix);
83 clusters.push(cluster);
90 pub fn new_random() -> Self {
91 let mut rng = RNG::new();
92 let mut clusters = Vec::with_capacity(256);
94 let pix = Pixel { r: rng.next(), g: rng.next(), b: rng.next() };
95 let cluster = Cluster::new(pix);
96 clusters.push(cluster);
102 fn sort<F>(arr: &mut [Pixel], idx: F) where F: Fn(&Pixel) -> u8 {
103 let mut dst = vec![Pixel::default(); arr.len()];
104 let mut counts = [0; 256];
105 for pix in arr.iter() {
106 counts[idx(pix) as usize] += 1;
108 let mut last = counts[0];
110 for count in counts.iter_mut().skip(1) {
115 for pix in arr.iter() {
116 let bucket = idx(pix) as usize;
117 dst[counts[bucket]] = *pix;
120 arr.copy_from_slice(dst.as_slice());
122 fn new_split(old_index: usize, entries: &[Entry], indices: &[usize]) -> Option<(Pixel, Pixel)> {
123 let mut max = Pixel { r: 0, g: 0, b: 0 };
124 let mut min = Pixel { r: 255, g: 255, b: 255 };
125 let mut found = false;
126 for (entry, idx) in entries.iter().zip(indices) {
127 if *idx == old_index {
128 max = max.max(entry.pix);
129 min = min.min(entry.pix);
136 let dr = max.r - min.r;
137 let dg = max.g - min.g;
138 let db = max.b - min.b;
139 let cent0 = Pixel { r: min.r + dr / 3, g: min.g + dg / 3, b: min.b + db / 3 };
140 let cent1 = Pixel { r: max.r - dr / 3, g: max.g - dg / 3, b: max.b - db / 3 };
143 fn old_centre(&self, old_index1: usize, old_index2: usize, entries: &[Entry], indices: &[usize]) -> Pixel {
144 let mut max = Pixel { r: 0, g: 0, b: 0 };
145 let mut min = Pixel { r: 255, g: 255, b: 255 };
146 let mut found = false;
147 for (entry, idx) in entries.iter().zip(indices) {
148 if *idx == old_index1 || *idx == old_index2 {
149 max = max.max(entry.pix);
150 min = min.min(entry.pix);
155 max = self.clusters[old_index1].centroid.max(self.clusters[old_index2].centroid);
156 min = self.clusters[old_index1].centroid.min(self.clusters[old_index2].centroid);
158 let dr = max.r - min.r;
159 let dg = max.g - min.g;
160 let db = max.b - min.b;
161 Pixel { r: min.r + dr / 2, g: min.g + dg / 2, b: min.b + db / 2 }
163 fn estimate_old(old_idx0: usize, old_idx1: usize, c: Pixel, entries: &[Entry], indices: &[usize]) -> u64 {
164 let mut clu = Cluster::new(c);
166 for (entry, idx) in entries.iter().zip(indices) {
167 if *idx == old_idx0 || *idx == old_idx1 {
169 count += entry.count;
176 fn estimate_new(c0: Pixel, c1: Pixel, old_idx: usize, entries: &[Entry], indices: &[usize]) -> u64 {
177 let mut clu0 = Cluster::new(c0);
178 let mut clu1 = Cluster::new(c1);
181 for (entry, idx) in entries.iter().zip(indices) {
183 if c0.dist(entry.pix) < c1.dist(entry.pix) {
184 clu0.add_dist(entry);
185 count0 += entry.count;
187 clu1.add_dist(entry);
188 count1 += entry.count;
196 clu0.dist + clu1.dist
198 #[allow(clippy::cognitive_complexity)]
199 pub fn quantise(&mut self, src: &[Pixel], dst: &mut [[u8; 3]; 256]) {
203 let mut old_cb: [Pixel; 256] = [Pixel::default(); 256];
204 let mut prev_dist = std::u64::MAX;
205 let mut dist = std::u64::MAX / 2;
206 let mut indices = Vec::with_capacity(src.len());
207 let mut pixels = Vec::with_capacity(src.len());
208 pixels.extend_from_slice(src);
209 Self::sort(pixels.as_mut_slice(), |pix| pix.r);
210 Self::sort(pixels.as_mut_slice(), |pix| pix.g);
211 Self::sort(pixels.as_mut_slice(), |pix| pix.b);
212 let mut entries = Vec::with_capacity(pixels.len() / 2);
213 let mut lastval = pixels[0];
215 for pix in pixels.iter().skip(1) {
219 entries.push(Entry { pix: lastval, count: run });
224 entries.push(Entry { pix: lastval, count: run });
227 let mut low_u: Vec<usize> = Vec::with_capacity(256);
228 let mut high_u: Vec<usize> = Vec::with_capacity(256);
229 let mut rng = RNG::new();
230 let mut iterations = 0usize;
231 let mut do_elbg_step = true;
232 while (iterations < 10) && (dist < prev_dist - prev_dist / 100) {
235 old_cb[i] = self.clusters[i].centroid;
236 self.clusters[i].reset();
238 // put pixels into the nearest clusters
240 for entry in entries.iter() {
242 let mut bestdist = std::u32::MAX;
243 for (i, cluster) in self.clusters.iter().enumerate() {
244 let dist = entry.pix.dist(cluster.centroid);
253 indices.push(bestidx);
254 self.clusters[bestidx].add_pixel(entry);
257 for cluster in self.clusters.iter_mut() {
258 cluster.calc_centroid();
261 for (idx, entry) in indices.iter().zip(entries.iter()) {
262 self.clusters[*idx].add_dist(entry);
264 for cluster in self.clusters.iter_mut() {
266 dist += cluster.dist;
269 let dmean = dist / 256;
272 let mut used = [false; 256];
273 for (i, cluster) in self.clusters.iter().enumerate() {
274 if cluster.dist < dmean {
276 } else if cluster.dist > dmean * 2 {
283 do_elbg_step = false;
284 for low_idx in low_u.iter() {
285 if high_u.is_empty() {
288 let high_idx_idx = (rng.next() as usize) % high_u.len();
289 let high_idx = high_u[high_idx_idx];
290 let mut closest_idx = *low_idx;
291 let mut closest_dist = std::u32::MAX;
292 let low_centr = self.clusters[*low_idx].centroid;
293 for i in 0..256 {//low_u.iter() {
294 if i == *low_idx || used[i] {
297 let dist = self.clusters[i].centroid.dist(low_centr);
298 if closest_dist > dist {
303 if closest_idx == *low_idx {
306 let old_dist = self.clusters[*low_idx].dist + self.clusters[closest_idx].dist + self.clusters[high_idx].dist;
307 let old_centr = self.old_centre(*low_idx, closest_idx, entries.as_slice(), indices.as_slice());
308 let ret = Self::new_split(high_idx, entries.as_slice(), indices.as_slice());
312 let (centr0, centr1) = ret.unwrap();
313 let dist_o = if old_dist > self.clusters[high_idx].dist {
314 Self::estimate_old(*low_idx, closest_idx, old_centr, entries.as_slice(), indices.as_slice())
316 let dist_n = Self::estimate_new(centr0, centr1, high_idx, entries.as_slice(), indices.as_slice());
317 if dist_o + dist_n < old_dist {
318 self.clusters[*low_idx ].centroid = old_centr;
319 self.clusters[closest_idx].centroid = centr0;
320 self.clusters[high_idx ].centroid = centr1;
321 used[*low_idx] = true;
322 used[closest_idx] = true;
323 used[high_idx] = true;
324 high_u.remove(high_idx_idx);
331 if dist < prev_dist {
333 old_cb[i] = self.clusters[i].centroid;
337 dst[i][0] = old_cb[i].r;
338 dst[i][1] = old_cb[i].g;
339 dst[i][2] = old_cb[i].b;