1// SPDX-License-Identifier: Apache-2.0
2// ----------------------------------------------------------------------------
3// Copyright 2011-2023 Arm Limited
4//
5// Licensed under the Apache License, Version 2.0 (the "License"); you may not
6// use this file except in compliance with the License. You may obtain a copy
7// of the License at:
8//
9// http://www.apache.org/licenses/LICENSE-2.0
10//
11// Unless required by applicable law or agreed to in writing, software
12// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
13// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
14// License for the specific language governing permissions and limitations
15// under the License.
16// ----------------------------------------------------------------------------
17
18#if !defined(ASTCENC_DECOMPRESS_ONLY)
19
20/**
21 * @brief Functions for angular-sum algorithm for weight alignment.
22 *
23 * This algorithm works as follows:
24 * - we compute a complex number P as (cos s*i, sin s*i) for each weight,
25 * where i is the input value and s is a scaling factor based on the spacing between the weights.
26 * - we then add together complex numbers for all the weights.
27 * - we then compute the length and angle of the resulting sum.
28 *
29 * This should produce the following results:
30 * - perfect alignment results in a vector whose length is equal to the sum of lengths of all inputs
31 * - even distribution results in a vector of length 0.
32 * - all samples identical results in perfect alignment for every scaling.
33 *
34 * For each scaling factor within a given set, we compute an alignment factor from 0 to 1. This
35 * should then result in some scalings standing out as having particularly good alignment factors;
36 * we can use this to produce a set of candidate scale/shift values for various quantization levels;
37 * we should then actually try them and see what happens.
38 */
39
40#include "astcenc_internal.h"
41#include "astcenc_vecmathlib.h"
42
43#include <stdio.h>
44#include <cassert>
45#include <cstring>
46
47static constexpr unsigned int ANGULAR_STEPS { 32 };
48
49static_assert((ANGULAR_STEPS % ASTCENC_SIMD_WIDTH) == 0,
50 "ANGULAR_STEPS must be multiple of ASTCENC_SIMD_WIDTH");
51
52static_assert(ANGULAR_STEPS >= 32,
53 "ANGULAR_STEPS must be at least max(steps_for_quant_level)");
54
55// Store a reduced sin/cos table for 64 possible weight values; this causes
56// slight quality loss compared to using sin() and cos() directly. Must be 2^N.
57static constexpr unsigned int SINCOS_STEPS { 64 };
58
59static const uint8_t steps_for_quant_level[12] {
60 2, 3, 4, 5, 6, 8, 10, 12, 16, 20, 24, 32
61};
62
63alignas(ASTCENC_VECALIGN) static float sin_table[SINCOS_STEPS][ANGULAR_STEPS];
64alignas(ASTCENC_VECALIGN) static float cos_table[SINCOS_STEPS][ANGULAR_STEPS];
65
66#if defined(ASTCENC_DIAGNOSTICS)
67 static bool print_once { true };
68#endif
69
70/* See header for documentation. */
71void prepare_angular_tables()
72{
73 for (unsigned int i = 0; i < ANGULAR_STEPS; i++)
74 {
75 float angle_step = static_cast<float>(i + 1);
76
77 for (unsigned int j = 0; j < SINCOS_STEPS; j++)
78 {
79 sin_table[j][i] = static_cast<float>(sinf((2.0f * astc::PI / (SINCOS_STEPS - 1.0f)) * angle_step * static_cast<float>(j)));
80 cos_table[j][i] = static_cast<float>(cosf((2.0f * astc::PI / (SINCOS_STEPS - 1.0f)) * angle_step * static_cast<float>(j)));
81 }
82 }
83}
84
85/**
86 * @brief Compute the angular alignment factors and offsets.
87 *
88 * @param weight_count The number of (decimated) weights.
89 * @param dec_weight_ideal_value The ideal decimated unquantized weight values.
90 * @param max_angular_steps The maximum number of steps to be tested.
91 * @param[out] offsets The output angular offsets array.
92 */
93static void compute_angular_offsets(
94 unsigned int weight_count,
95 const float* dec_weight_ideal_value,
96 unsigned int max_angular_steps,
97 float* offsets
98) {
99 promise(weight_count > 0);
100 promise(max_angular_steps > 0);
101
102 alignas(ASTCENC_VECALIGN) int isamplev[BLOCK_MAX_WEIGHTS];
103
104 // Precompute isample; arrays are always allocated 64 elements long
105 for (unsigned int i = 0; i < weight_count; i += ASTCENC_SIMD_WIDTH)
106 {
107 // Add 2^23 and interpreting bits extracts round-to-nearest int
108 vfloat sample = loada(dec_weight_ideal_value + i) * (SINCOS_STEPS - 1.0f) + vfloat(12582912.0f);
109 vint isample = float_as_int(sample) & vint((SINCOS_STEPS - 1));
110 storea(isample, isamplev + i);
111 }
112
113 // Arrays are multiple of SIMD width (ANGULAR_STEPS), safe to overshoot max
114 vfloat mult = vfloat(1.0f / (2.0f * astc::PI));
115
116 for (unsigned int i = 0; i < max_angular_steps; i += ASTCENC_SIMD_WIDTH)
117 {
118 vfloat anglesum_x = vfloat::zero();
119 vfloat anglesum_y = vfloat::zero();
120
121 for (unsigned int j = 0; j < weight_count; j++)
122 {
123 int isample = isamplev[j];
124 anglesum_x += loada(cos_table[isample] + i);
125 anglesum_y += loada(sin_table[isample] + i);
126 }
127
128 vfloat angle = atan2(anglesum_y, anglesum_x);
129 vfloat ofs = angle * mult;
130 storea(ofs, offsets + i);
131 }
132}
133
134/**
135 * @brief For a given step size compute the lowest and highest weight.
136 *
137 * Compute the lowest and highest weight that results from quantizing using the given stepsize and
138 * offset, and then compute the resulting error. The cut errors indicate the error that results from
139 * forcing samples that should have had one weight value one step up or down.
140 *
141 * @param weight_count The number of (decimated) weights.
142 * @param dec_weight_ideal_value The ideal decimated unquantized weight values.
143 * @param max_angular_steps The maximum number of steps to be tested.
144 * @param max_quant_steps The maximum quantization level to be tested.
145 * @param offsets The angular offsets array.
146 * @param[out] lowest_weight Per angular step, the lowest weight.
147 * @param[out] weight_span Per angular step, the span between lowest and highest weight.
148 * @param[out] error Per angular step, the error.
149 * @param[out] cut_low_weight_error Per angular step, the low weight cut error.
150 * @param[out] cut_high_weight_error Per angular step, the high weight cut error.
151 */
152static void compute_lowest_and_highest_weight(
153 unsigned int weight_count,
154 const float* dec_weight_ideal_value,
155 unsigned int max_angular_steps,
156 unsigned int max_quant_steps,
157 const float* offsets,
158 float* lowest_weight,
159 int* weight_span,
160 float* error,
161 float* cut_low_weight_error,
162 float* cut_high_weight_error
163) {
164 promise(weight_count > 0);
165 promise(max_angular_steps > 0);
166
167 vfloat rcp_stepsize = vfloat::lane_id() + vfloat(1.0f);
168
169 // Arrays are ANGULAR_STEPS long, so always safe to run full vectors
170 for (unsigned int sp = 0; sp < max_angular_steps; sp += ASTCENC_SIMD_WIDTH)
171 {
172 vfloat minidx(128.0f);
173 vfloat maxidx(-128.0f);
174 vfloat errval = vfloat::zero();
175 vfloat cut_low_weight_err = vfloat::zero();
176 vfloat cut_high_weight_err = vfloat::zero();
177 vfloat offset = loada(offsets + sp);
178
179 for (unsigned int j = 0; j < weight_count; j++)
180 {
181 vfloat sval = load1(dec_weight_ideal_value + j) * rcp_stepsize - offset;
182 vfloat svalrte = round(sval);
183 vfloat diff = sval - svalrte;
184 errval += diff * diff;
185
186 // Reset tracker on min hit
187 vmask mask = svalrte < minidx;
188 minidx = select(minidx, svalrte, mask);
189 cut_low_weight_err = select(cut_low_weight_err, vfloat::zero(), mask);
190
191 // Accumulate on min hit
192 mask = svalrte == minidx;
193 vfloat accum = cut_low_weight_err + vfloat(1.0f) - vfloat(2.0f) * diff;
194 cut_low_weight_err = select(cut_low_weight_err, accum, mask);
195
196 // Reset tracker on max hit
197 mask = svalrte > maxidx;
198 maxidx = select(maxidx, svalrte, mask);
199 cut_high_weight_err = select(cut_high_weight_err, vfloat::zero(), mask);
200
201 // Accumulate on max hit
202 mask = svalrte == maxidx;
203 accum = cut_high_weight_err + vfloat(1.0f) + vfloat(2.0f) * diff;
204 cut_high_weight_err = select(cut_high_weight_err, accum, mask);
205 }
206
207 // Write out min weight and weight span; clamp span to a usable range
208 vint span = float_to_int(maxidx - minidx + vfloat(1));
209 span = min(span, vint(max_quant_steps + 3));
210 span = max(span, vint(2));
211 storea(minidx, lowest_weight + sp);
212 storea(span, weight_span + sp);
213
214 // The cut_(lowest/highest)_weight_error indicate the error that results from forcing
215 // samples that should have had the weight value one step (up/down).
216 vfloat ssize = 1.0f / rcp_stepsize;
217 vfloat errscale = ssize * ssize;
218 storea(errval * errscale, error + sp);
219 storea(cut_low_weight_err * errscale, cut_low_weight_error + sp);
220 storea(cut_high_weight_err * errscale, cut_high_weight_error + sp);
221
222 rcp_stepsize = rcp_stepsize + vfloat(ASTCENC_SIMD_WIDTH);
223 }
224}
225
226/**
227 * @brief The main function for the angular algorithm.
228 *
229 * @param weight_count The number of (decimated) weights.
230 * @param dec_weight_ideal_value The ideal decimated unquantized weight values.
231 * @param max_quant_level The maximum quantization level to be tested.
232 * @param[out] low_value Per angular step, the lowest weight value.
233 * @param[out] high_value Per angular step, the highest weight value.
234 */
235static void compute_angular_endpoints_for_quant_levels(
236 unsigned int weight_count,
237 const float* dec_weight_ideal_value,
238 unsigned int max_quant_level,
239 float low_value[TUNE_MAX_ANGULAR_QUANT + 1],
240 float high_value[TUNE_MAX_ANGULAR_QUANT + 1]
241) {
242 unsigned int max_quant_steps = steps_for_quant_level[max_quant_level];
243 unsigned int max_angular_steps = steps_for_quant_level[max_quant_level];
244
245 alignas(ASTCENC_VECALIGN) float angular_offsets[ANGULAR_STEPS];
246
247 compute_angular_offsets(weight_count, dec_weight_ideal_value,
248 max_angular_steps, angular_offsets);
249
250 alignas(ASTCENC_VECALIGN) float lowest_weight[ANGULAR_STEPS];
251 alignas(ASTCENC_VECALIGN) int32_t weight_span[ANGULAR_STEPS];
252 alignas(ASTCENC_VECALIGN) float error[ANGULAR_STEPS];
253 alignas(ASTCENC_VECALIGN) float cut_low_weight_error[ANGULAR_STEPS];
254 alignas(ASTCENC_VECALIGN) float cut_high_weight_error[ANGULAR_STEPS];
255
256 compute_lowest_and_highest_weight(weight_count, dec_weight_ideal_value,
257 max_angular_steps, max_quant_steps,
258 angular_offsets, lowest_weight, weight_span, error,
259 cut_low_weight_error, cut_high_weight_error);
260
261 // For each quantization level, find the best error terms. Use packed vectors so data-dependent
262 // branches can become selects. This involves some integer to float casts, but the values are
263 // small enough so they never round the wrong way.
264 vfloat4 best_results[36];
265
266 // Initialize the array to some safe defaults
267 promise(max_quant_steps > 0);
268 for (unsigned int i = 0; i < (max_quant_steps + 4); i++)
269 {
270 // Lane<0> = Best error
271 // Lane<1> = Best scale; -1 indicates no solution found
272 // Lane<2> = Cut low weight
273 best_results[i] = vfloat4(ERROR_CALC_DEFAULT, -1.0f, 0.0f, 0.0f);
274 }
275
276 promise(max_angular_steps > 0);
277 for (unsigned int i = 0; i < max_angular_steps; i++)
278 {
279 float i_flt = static_cast<float>(i);
280
281 int idx_span = weight_span[i];
282
283 float error_cut_low = error[i] + cut_low_weight_error[i];
284 float error_cut_high = error[i] + cut_high_weight_error[i];
285 float error_cut_low_high = error[i] + cut_low_weight_error[i] + cut_high_weight_error[i];
286
287 // Check best error against record N
288 vfloat4 best_result = best_results[idx_span];
289 vfloat4 new_result = vfloat4(error[i], i_flt, 0.0f, 0.0f);
290 vmask4 mask = vfloat4(best_result.lane<0>()) > vfloat4(error[i]);
291 best_results[idx_span] = select(best_result, new_result, mask);
292
293 // Check best error against record N-1 with either cut low or cut high
294 best_result = best_results[idx_span - 1];
295
296 new_result = vfloat4(error_cut_low, i_flt, 1.0f, 0.0f);
297 mask = vfloat4(best_result.lane<0>()) > vfloat4(error_cut_low);
298 best_result = select(best_result, new_result, mask);
299
300 new_result = vfloat4(error_cut_high, i_flt, 0.0f, 0.0f);
301 mask = vfloat4(best_result.lane<0>()) > vfloat4(error_cut_high);
302 best_results[idx_span - 1] = select(best_result, new_result, mask);
303
304 // Check best error against record N-2 with both cut low and high
305 best_result = best_results[idx_span - 2];
306 new_result = vfloat4(error_cut_low_high, i_flt, 1.0f, 0.0f);
307 mask = vfloat4(best_result.lane<0>()) > vfloat4(error_cut_low_high);
308 best_results[idx_span - 2] = select(best_result, new_result, mask);
309 }
310
311 for (unsigned int i = 0; i <= max_quant_level; i++)
312 {
313 unsigned int q = steps_for_quant_level[i];
314 int bsi = static_cast<int>(best_results[q].lane<1>());
315
316 // Did we find anything?
317#if defined(ASTCENC_DIAGNOSTICS)
318 if ((bsi < 0) && print_once)
319 {
320 print_once = false;
321 printf("INFO: Unable to find full encoding within search error limit.\n\n");
322 }
323#endif
324
325 bsi = astc::max(0, bsi);
326
327 float lwi = lowest_weight[bsi] + best_results[q].lane<2>();
328 float hwi = lwi + static_cast<float>(q) - 1.0f;
329
330 float stepsize = 1.0f / (1.0f + static_cast<float>(bsi));
331 low_value[i] = (angular_offsets[bsi] + lwi) * stepsize;
332 high_value[i] = (angular_offsets[bsi] + hwi) * stepsize;
333 }
334}
335
336/* See header for documentation. */
337void compute_angular_endpoints_1plane(
338 bool only_always,
339 const block_size_descriptor& bsd,
340 const float* dec_weight_ideal_value,
341 unsigned int max_weight_quant,
342 compression_working_buffers& tmpbuf
343) {
344 float (&low_value)[WEIGHTS_MAX_BLOCK_MODES] = tmpbuf.weight_low_value1;
345 float (&high_value)[WEIGHTS_MAX_BLOCK_MODES] = tmpbuf.weight_high_value1;
346
347 float (&low_values)[WEIGHTS_MAX_DECIMATION_MODES][TUNE_MAX_ANGULAR_QUANT + 1] = tmpbuf.weight_low_values1;
348 float (&high_values)[WEIGHTS_MAX_DECIMATION_MODES][TUNE_MAX_ANGULAR_QUANT + 1] = tmpbuf.weight_high_values1;
349
350 unsigned int max_decimation_modes = only_always ? bsd.decimation_mode_count_always
351 : bsd.decimation_mode_count_selected;
352 promise(max_decimation_modes > 0);
353 for (unsigned int i = 0; i < max_decimation_modes; i++)
354 {
355 const decimation_mode& dm = bsd.decimation_modes[i];
356 if (!dm.is_ref_1plane(static_cast<quant_method>(max_weight_quant)))
357 {
358 continue;
359 }
360
361 unsigned int weight_count = bsd.get_decimation_info(i).weight_count;
362
363 unsigned int max_precision = dm.maxprec_1plane;
364 if (max_precision > TUNE_MAX_ANGULAR_QUANT)
365 {
366 max_precision = TUNE_MAX_ANGULAR_QUANT;
367 }
368
369 if (max_precision > max_weight_quant)
370 {
371 max_precision = max_weight_quant;
372 }
373
374 compute_angular_endpoints_for_quant_levels(
375 weight_count,
376 dec_weight_ideal_value + i * BLOCK_MAX_WEIGHTS,
377 max_precision, low_values[i], high_values[i]);
378 }
379
380 unsigned int max_block_modes = only_always ? bsd.block_mode_count_1plane_always
381 : bsd.block_mode_count_1plane_selected;
382 promise(max_block_modes > 0);
383 for (unsigned int i = 0; i < max_block_modes; i++)
384 {
385 const block_mode& bm = bsd.block_modes[i];
386 assert(!bm.is_dual_plane);
387
388 unsigned int quant_mode = bm.quant_mode;
389 unsigned int decim_mode = bm.decimation_mode;
390
391 if (quant_mode <= TUNE_MAX_ANGULAR_QUANT)
392 {
393 low_value[i] = low_values[decim_mode][quant_mode];
394 high_value[i] = high_values[decim_mode][quant_mode];
395 }
396 else
397 {
398 low_value[i] = 0.0f;
399 high_value[i] = 1.0f;
400 }
401 }
402}
403
404/* See header for documentation. */
405void compute_angular_endpoints_2planes(
406 const block_size_descriptor& bsd,
407 const float* dec_weight_ideal_value,
408 unsigned int max_weight_quant,
409 compression_working_buffers& tmpbuf
410) {
411 float (&low_value1)[WEIGHTS_MAX_BLOCK_MODES] = tmpbuf.weight_low_value1;
412 float (&high_value1)[WEIGHTS_MAX_BLOCK_MODES] = tmpbuf.weight_high_value1;
413 float (&low_value2)[WEIGHTS_MAX_BLOCK_MODES] = tmpbuf.weight_low_value2;
414 float (&high_value2)[WEIGHTS_MAX_BLOCK_MODES] = tmpbuf.weight_high_value2;
415
416 float (&low_values1)[WEIGHTS_MAX_DECIMATION_MODES][TUNE_MAX_ANGULAR_QUANT + 1] = tmpbuf.weight_low_values1;
417 float (&high_values1)[WEIGHTS_MAX_DECIMATION_MODES][TUNE_MAX_ANGULAR_QUANT + 1] = tmpbuf.weight_high_values1;
418 float (&low_values2)[WEIGHTS_MAX_DECIMATION_MODES][TUNE_MAX_ANGULAR_QUANT + 1] = tmpbuf.weight_low_values2;
419 float (&high_values2)[WEIGHTS_MAX_DECIMATION_MODES][TUNE_MAX_ANGULAR_QUANT + 1] = tmpbuf.weight_high_values2;
420
421 promise(bsd.decimation_mode_count_selected > 0);
422 for (unsigned int i = 0; i < bsd.decimation_mode_count_selected; i++)
423 {
424 const decimation_mode& dm = bsd.decimation_modes[i];
425 if (!dm.is_ref_2plane(static_cast<quant_method>(max_weight_quant)))
426 {
427 continue;
428 }
429
430 unsigned int weight_count = bsd.get_decimation_info(i).weight_count;
431
432 unsigned int max_precision = dm.maxprec_2planes;
433 if (max_precision > TUNE_MAX_ANGULAR_QUANT)
434 {
435 max_precision = TUNE_MAX_ANGULAR_QUANT;
436 }
437
438 if (max_precision > max_weight_quant)
439 {
440 max_precision = max_weight_quant;
441 }
442
443 compute_angular_endpoints_for_quant_levels(
444 weight_count,
445 dec_weight_ideal_value + i * BLOCK_MAX_WEIGHTS,
446 max_precision, low_values1[i], high_values1[i]);
447
448 compute_angular_endpoints_for_quant_levels(
449 weight_count,
450 dec_weight_ideal_value + i * BLOCK_MAX_WEIGHTS + WEIGHTS_PLANE2_OFFSET,
451 max_precision, low_values2[i], high_values2[i]);
452 }
453
454 unsigned int start = bsd.block_mode_count_1plane_selected;
455 unsigned int end = bsd.block_mode_count_1plane_2plane_selected;
456 for (unsigned int i = start; i < end; i++)
457 {
458 const block_mode& bm = bsd.block_modes[i];
459 unsigned int quant_mode = bm.quant_mode;
460 unsigned int decim_mode = bm.decimation_mode;
461
462 if (quant_mode <= TUNE_MAX_ANGULAR_QUANT)
463 {
464 low_value1[i] = low_values1[decim_mode][quant_mode];
465 high_value1[i] = high_values1[decim_mode][quant_mode];
466 low_value2[i] = low_values2[decim_mode][quant_mode];
467 high_value2[i] = high_values2[decim_mode][quant_mode];
468 }
469 else
470 {
471 low_value1[i] = 0.0f;
472 high_value1[i] = 1.0f;
473 low_value2[i] = 0.0f;
474 high_value2[i] = 1.0f;
475 }
476 }
477}
478
479#endif
480