1 // Copyright (c) Facebook, Inc. and its affiliates.
2 // All rights reserved.
3 //
4 // Copyright 2019 Google LLC
5 //
6 // This source code is licensed under the BSD-style license found in the
7 // LICENSE file in the root directory of this source tree.
8
9 #include <assert.h>
10 #include <stdint.h>
11 #include <stddef.h>
12
13 #include <xnnpack/math.h>
14 #include <xnnpack/requantization-stubs.h>
15
16
xnn_qs8_requantize_rndna__scalar_unsigned32(size_t n,const int32_t * input,float scale,int8_t zero_point,int8_t qmin,int8_t qmax,int8_t * output)17 void xnn_qs8_requantize_rndna__scalar_unsigned32(
18 size_t n,
19 const int32_t* input,
20 float scale,
21 int8_t zero_point,
22 int8_t qmin,
23 int8_t qmax,
24 int8_t* output)
25 {
26 assert(n % 4 == 0);
27 assert(scale < 1.0f);
28 assert(scale >= 0x1.0p-32f);
29
30 const uint32_t scale_bits = float_as_uint32(scale);
31 const uint32_t multiplier = (scale_bits << 8) | UINT32_C(0x80000000);
32 const uint32_t shift = 127 + 31 - (scale_bits >> 23);
33 assert(shift >= 32);
34 assert(shift < 64);
35
36 const uint64_t rounding = UINT64_C(1) << (shift - 1);
37 const uint32_t rounding_hi = (uint32_t)(rounding >> 32);
38 const uint32_t rounding_lo = (uint32_t) rounding;
39 const uint32_t shift_minus_32 = shift - 32;
40 const int32_t smin = (int32_t) qmin - (int32_t) zero_point;
41 const int32_t smax = (int32_t) qmax - (int32_t) zero_point;
42 for (; n != 0; n -= 4) {
43 const int32_t x = input[0];
44 const int32_t y = input[1];
45 const int32_t z = input[2];
46 const int32_t w = input[3];
47 input += 4;
48
49 // Compute absolute value of input as unsigned 32-bit int.
50 // All further computations will work with unsigned values to avoid undefined behaviour on signed operations.
51 const uint32_t x_abs = (x >= 0) ? (uint32_t) x : -(uint32_t) x;
52 const uint32_t y_abs = (y >= 0) ? (uint32_t) y : -(uint32_t) y;
53 const uint32_t z_abs = (z >= 0) ? (uint32_t) z : -(uint32_t) z;
54 const uint32_t w_abs = (w >= 0) ? (uint32_t) w : -(uint32_t) w;
55
56 // Compute full 64-bit product of 32-bit factors.
57 const uint64_t x_product = (uint64_t) x_abs * (uint64_t) multiplier;
58 const uint64_t y_product = (uint64_t) y_abs * (uint64_t) multiplier;
59 const uint64_t z_product = (uint64_t) z_abs * (uint64_t) multiplier;
60 const uint64_t w_product = (uint64_t) w_abs * (uint64_t) multiplier;
61
62 // Shift the full 64-bit product right with rounding.
63 // Rounding is performed towards closest integer, with midpoints rounded up (same as away from zero).
64 //
65 // Generally, this operation requires both 64-bit addition and 64-bit shift, but we use two tricks to replace
66 // 64-bit operations with 32-bit operations.
67 //
68 // To avoid full 64-bit addition we make use of three facts:
69 // - 64-bit rounding value added before the shift is a power of 2, and thus has only one bit set.
70 // - When 0x1.0p-32f <= scale < 0x1.0p-31f, then the non-zero bit in rounding is in the low 32 bits, and
71 // rounding is exactly 0x80000000 (2**31), because rounding is 2**(scale-1) and scale >= 32. In this case,
72 // addition of rounding can affect high 32 bits of the product only through overflow, which happens if
73 // low 32-bit part of the product equals or exceeds 0x80000000. We can reformulate the latter condition
74 // as low 32-bit part of the product has the bit 31 set, and then overflow happens if both the low 32-bit part
75 // of the product and the low 32-bit part of the rounding value have bit 31 set. Since 32-bit numbers with the
76 // bit 31 set are negative when interpreted as signed integers, we can check the overflow condition as
77 // (int32_t) (LOW(product) & LOW(rounding)) < 0
78 // - When 0x1.0p-31f <= scale < 1.0f, then the non-zero bit is in the high 32 bits of rounding. We just need
79 // to do 32-bit addition of high 32 bits of rounding and high 32 bits of product. This addition never
80 // overflows because product <= 0x80000000 * 0xFFFFFF00 < 2**63 and rounding = 2**(scale-1) <= 2**62.
81 //
82 // To avoid full 64-bit shift, we leverage the fact that shift >= 32, and do it in two steps:
83 // - Shift by 32, which can be implemented by extacting the high 32-bit word on 32-bit systems.
84 // - Shift by (shift - 32), which can be implemented as a 32-bit shift of high word of addition result.
85 const uint32_t x_carry_lo = (uint32_t) ((int32_t) ((uint32_t) x_product & rounding_lo) < 0);
86 const uint32_t y_carry_lo = (uint32_t) ((int32_t) ((uint32_t) y_product & rounding_lo) < 0);
87 const uint32_t z_carry_lo = (uint32_t) ((int32_t) ((uint32_t) z_product & rounding_lo) < 0);
88 const uint32_t w_carry_lo = (uint32_t) ((int32_t) ((uint32_t) w_product & rounding_lo) < 0);
89
90 const uint32_t x_product_hi = (uint32_t) (x_product >> 32);
91 const uint32_t y_product_hi = (uint32_t) (y_product >> 32);
92 const uint32_t z_product_hi = (uint32_t) (z_product >> 32);
93 const uint32_t w_product_hi = (uint32_t) (w_product >> 32);
94
95 const uint32_t x_abs_scaled = (uint32_t) (x_product_hi + rounding_hi + x_carry_lo) >> shift_minus_32;
96 const uint32_t y_abs_scaled = (uint32_t) (y_product_hi + rounding_hi + y_carry_lo) >> shift_minus_32;
97 const uint32_t z_abs_scaled = (uint32_t) (z_product_hi + rounding_hi + z_carry_lo) >> shift_minus_32;
98 const uint32_t w_abs_scaled = (uint32_t) (w_product_hi + rounding_hi + w_carry_lo) >> shift_minus_32;
99
100 // Copy the sign of input to scaled absolute input value.
101 const int32_t x_scaled = (int32_t) (x >= 0 ? x_abs_scaled : -x_abs_scaled);
102 const int32_t y_scaled = (int32_t) (y >= 0 ? y_abs_scaled : -y_abs_scaled);
103 const int32_t z_scaled = (int32_t) (z >= 0 ? z_abs_scaled : -z_abs_scaled);
104 const int32_t w_scaled = (int32_t) (w >= 0 ? w_abs_scaled : -w_abs_scaled);
105
106 // Clamp scaled value with zero point between (qmin - zero point) and (qmax - zero point).
107 const int32_t x_clamped = math_min_s32(math_max_s32(x_scaled, smin), smax);
108 const int32_t y_clamped = math_min_s32(math_max_s32(y_scaled, smin), smax);
109 const int32_t z_clamped = math_min_s32(math_max_s32(z_scaled, smin), smax);
110 const int32_t w_clamped = math_min_s32(math_max_s32(w_scaled, smin), smax);
111
112 // Add zero point to clamped value.
113 // The result is guaranteed to be in [qmin, qmax] range.
114 //
115 // This addition can not be safely done before clamping, because scaled values are in [-2147483520, 2147483519]
116 // range, so addition of zero point (which can be up to 127) can overflow signed 32-bit integer.
117 const int32_t x_biased = x_clamped + zero_point;
118 const int32_t y_biased = y_clamped + zero_point;
119 const int32_t z_biased = z_clamped + zero_point;
120 const int32_t w_biased = w_clamped + zero_point;
121
122 output[0] = (int8_t) x_biased;
123 output[1] = (int8_t) y_biased;
124 output[2] = (int8_t) z_biased;
125 output[3] = (int8_t) w_biased;
126 output += 4;
127 }
128 }
129