1 //===-- Fixed Point Converter for printf ------------------------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef LLVM_LIBC_SRC_STDIO_PRINTF_CORE_FIXED_CONVERTER_H 10 #define LLVM_LIBC_SRC_STDIO_PRINTF_CORE_FIXED_CONVERTER_H 11 12 #include "include/llvm-libc-macros/stdfix-macros.h" 13 #include "src/__support/CPP/string_view.h" 14 #include "src/__support/ctype_utils.h" 15 #include "src/__support/fixed_point/fx_bits.h" 16 #include "src/__support/fixed_point/fx_rep.h" 17 #include "src/__support/integer_to_string.h" 18 #include "src/__support/libc_assert.h" 19 #include "src/__support/macros/config.h" 20 #include "src/stdio/printf_core/converter_utils.h" 21 #include "src/stdio/printf_core/core_structs.h" 22 #include "src/stdio/printf_core/writer.h" 23 24 #include <inttypes.h> 25 #include <stddef.h> 26 27 namespace LIBC_NAMESPACE_DECL { 28 namespace printf_core { 29 30 // This is just for assertions. It will be compiled out for release builds. 31 LIBC_INLINE constexpr uint32_t const_ten_exp(uint32_t exponent) { 32 uint32_t result = 1; 33 LIBC_ASSERT(exponent < 11); 34 for (uint32_t i = 0; i < exponent; ++i) 35 result *= 10; 36 37 return result; 38 } 39 40 #define READ_FX_BITS(TYPE) \ 41 do { \ 42 auto fixed_bits = fixed_point::FXBits<TYPE>( \ 43 fixed_point::FXRep<TYPE>::StorageType(to_conv.conv_val_raw)); \ 44 integral = fixed_bits.get_integral(); \ 45 fractional = fixed_bits.get_fraction(); \ 46 exponent = fixed_bits.get_exponent(); \ 47 is_negative = fixed_bits.get_sign(); \ 48 } while (false) 49 50 #define APPLY_FX_LENGTH_MODIFIER(LENGTH_MODIFIER) \ 51 do { \ 52 if (to_conv.conv_name == 'r') { \ 53 READ_FX_BITS(LENGTH_MODIFIER fract); \ 54 } else if (to_conv.conv_name == 'R') { \ 55 READ_FX_BITS(unsigned LENGTH_MODIFIER fract); \ 56 } else if (to_conv.conv_name == 'k') { \ 57 READ_FX_BITS(LENGTH_MODIFIER accum); \ 58 } else if (to_conv.conv_name == 'K') { \ 59 READ_FX_BITS(unsigned LENGTH_MODIFIER accum); \ 60 } else { \ 61 LIBC_ASSERT(false && "Invalid conversion name passed to convert_fixed"); \ 62 return FIXED_POINT_CONVERSION_ERROR; \ 63 } \ 64 } while (false) 65 66 LIBC_INLINE int convert_fixed(Writer *writer, const FormatSection &to_conv) { 67 // Long accum should be the largest type, so we can store all the smaller 68 // numbers in things sized for it. 69 using LARep = fixed_point::FXRep<unsigned long accum>; 70 using StorageType = LARep::StorageType; 71 72 FormatFlags flags = to_conv.flags; 73 74 bool is_negative; 75 int exponent; 76 StorageType integral; 77 StorageType fractional; 78 79 // r = fract 80 // k = accum 81 // lowercase = signed 82 // uppercase = unsigned 83 // h = short 84 // l = long 85 // any other length modifier has no effect 86 87 if (to_conv.length_modifier == LengthModifier::h) { 88 APPLY_FX_LENGTH_MODIFIER(short); 89 } else if (to_conv.length_modifier == LengthModifier::l) { 90 APPLY_FX_LENGTH_MODIFIER(long); 91 } else { 92 APPLY_FX_LENGTH_MODIFIER(); 93 } 94 95 LIBC_ASSERT(static_cast<size_t>(exponent) <= 96 (sizeof(StorageType) - sizeof(uint32_t)) * CHAR_BIT && 97 "StorageType must be large enough to hold the fractional " 98 "component multiplied by a 32 bit number."); 99 100 // If to_conv doesn't specify a precision, the precision defaults to 6. 101 const size_t precision = to_conv.precision < 0 ? 6 : to_conv.precision; 102 bool has_decimal_point = 103 (precision > 0) || ((flags & FormatFlags::ALTERNATE_FORM) != 0); 104 105 // The number of non-zero digits below the decimal point for a negative power 106 // of 2 in base 10 is equal to the magnitude of the power of 2. 107 108 // A quick proof: 109 // Let p be any positive integer. 110 // Let e = 2^(-p) 111 // Let t be a positive integer such that e * 10^t is an integer. 112 // By definition: The smallest allowed value of t must be equal to the number 113 // of non-zero digits below the decimal point in e. 114 // If we evaluate e * 10^t we get the following: 115 // e * 10^t = 2^(-p) * 10*t = 2^(-p) * 2^t * 5^t = 5^t * 2^(t-p) 116 // For 5^t * 2^(t-p) to be an integer, both exponents must be non-negative, 117 // since 5 and 2 are coprime. 118 // The smallest value of t such that t-p is non-negative is p. 119 // Therefor, the number of non-zero digits below the decimal point for a given 120 // negative power of 2 "p" is equal to the value of p. 121 122 constexpr size_t MAX_FRACTION_DIGITS = LARep::FRACTION_LEN; 123 124 char fraction_digits[MAX_FRACTION_DIGITS]; 125 126 size_t valid_fraction_digits = 0; 127 128 // TODO: Factor this part out 129 while (fractional > 0) { 130 uint32_t cur_digits = 0; 131 // 10^9 is used since it's the largest power of 10 that fits in a uint32_t 132 constexpr uint32_t TEN_EXP_NINE = 1000000000; 133 constexpr size_t DIGITS_PER_BLOCK = 9; 134 135 // Multiply by 10^9, then grab the digits above the decimal point, then 136 // clear those digits in fractional. 137 fractional = fractional * TEN_EXP_NINE; 138 cur_digits = static_cast<uint32_t>(fractional >> exponent); 139 fractional = fractional % (StorageType(1) << exponent); 140 141 // we add TEN_EXP_NINE to force leading zeroes to show up, then we skip the 142 // first digit in the loop. 143 const IntegerToString<uint32_t> cur_fractional_digits(cur_digits + 144 TEN_EXP_NINE); 145 for (size_t i = 0; 146 i < DIGITS_PER_BLOCK && valid_fraction_digits < MAX_FRACTION_DIGITS; 147 ++i, ++valid_fraction_digits) 148 fraction_digits[valid_fraction_digits] = 149 cur_fractional_digits.view()[i + 1]; 150 151 if (valid_fraction_digits >= MAX_FRACTION_DIGITS) { 152 LIBC_ASSERT(fractional == 0 && "If the fraction digit buffer is full, " 153 "there should be no remaining digits."); 154 /* 155 A visual explanation of what this assert is checking: 156 157 32 digits (max for 32 bit fract) 158 +------------------------------++--+--- must be zero 159 | || | 160 123456789012345678901234567890120000 161 | || || || | 162 +-------++-------++-------++-------+ 163 9 digit blocks 164 */ 165 LIBC_ASSERT(cur_digits % const_ten_exp( 166 DIGITS_PER_BLOCK - 167 (MAX_FRACTION_DIGITS % DIGITS_PER_BLOCK)) == 168 0 && 169 "Digits after the MAX_FRACTION_DIGITS should all be zero."); 170 valid_fraction_digits = MAX_FRACTION_DIGITS; 171 } 172 } 173 174 if (precision < valid_fraction_digits) { 175 // Handle rounding. Just do round to nearest, tie to even since it's 176 // unspecified. 177 RoundDirection round; 178 char first_digit_after = fraction_digits[precision]; 179 if (internal::b36_char_to_int(first_digit_after) > 5) { 180 round = RoundDirection::Up; 181 } else if (internal::b36_char_to_int(first_digit_after) < 5) { 182 round = RoundDirection::Down; 183 } else { 184 // first_digit_after == '5' 185 // need to check the remaining digits, but default to even. 186 round = RoundDirection::Even; 187 for (size_t cur_digit_index = precision + 1; 188 cur_digit_index + 1 < valid_fraction_digits; ++cur_digit_index) { 189 if (fraction_digits[cur_digit_index] != '0') { 190 round = RoundDirection::Up; 191 break; 192 } 193 } 194 } 195 196 // If we need to actually perform rounding, do so. 197 if (round == RoundDirection::Up || round == RoundDirection::Even) { 198 bool keep_rounding = true; 199 int digit_to_round = static_cast<int>(precision) - 1; 200 for (; digit_to_round >= 0 && keep_rounding; --digit_to_round) { 201 keep_rounding = false; 202 char cur_digit = fraction_digits[digit_to_round]; 203 // if the digit should not be rounded up 204 if (round == RoundDirection::Even && 205 (internal::b36_char_to_int(cur_digit) % 2) == 0) { 206 // break out of the loop 207 break; 208 } 209 fraction_digits[digit_to_round] += 1; 210 211 // if the digit was a 9, instead replace with a 0. 212 if (cur_digit == '9') { 213 fraction_digits[digit_to_round] = '0'; 214 keep_rounding = true; 215 } 216 } 217 218 // if every digit below the decimal point was rounded up but we need to 219 // keep rounding 220 if (keep_rounding && 221 (round == RoundDirection::Up || 222 (round == RoundDirection::Even && ((integral % 2) == 1)))) { 223 // add one to the integral portion to round it up. 224 ++integral; 225 } 226 } 227 228 valid_fraction_digits = precision; 229 } 230 231 const IntegerToString<StorageType> integral_str(integral); 232 233 // these are signed to prevent underflow due to negative values. The 234 // eventual values will always be non-negative. 235 size_t trailing_zeroes = 0; 236 int padding; 237 238 // If the precision is greater than the actual result, pad with 0s 239 if (precision > valid_fraction_digits) 240 trailing_zeroes = precision - (valid_fraction_digits); 241 242 constexpr cpp::string_view DECIMAL_POINT("."); 243 244 char sign_char = 0; 245 246 // Check if the conv name is uppercase 247 if (internal::isupper(to_conv.conv_name)) { 248 // These flags are only for signed conversions, so this removes them if the 249 // conversion is unsigned. 250 flags = FormatFlags(flags & 251 ~(FormatFlags::FORCE_SIGN | FormatFlags::SPACE_PREFIX)); 252 } 253 254 if (is_negative) 255 sign_char = '-'; 256 else if ((flags & FormatFlags::FORCE_SIGN) == FormatFlags::FORCE_SIGN) 257 sign_char = '+'; // FORCE_SIGN has precedence over SPACE_PREFIX 258 else if ((flags & FormatFlags::SPACE_PREFIX) == FormatFlags::SPACE_PREFIX) 259 sign_char = ' '; 260 261 padding = static_cast<int>(to_conv.min_width - (sign_char > 0 ? 1 : 0) - 262 integral_str.size() - 263 static_cast<int>(has_decimal_point) - 264 valid_fraction_digits - trailing_zeroes); 265 if (padding < 0) 266 padding = 0; 267 268 if ((flags & FormatFlags::LEFT_JUSTIFIED) == FormatFlags::LEFT_JUSTIFIED) { 269 // The pattern is (sign), integral, (.), (fraction), (zeroes), (spaces) 270 if (sign_char > 0) 271 RET_IF_RESULT_NEGATIVE(writer->write(sign_char)); 272 RET_IF_RESULT_NEGATIVE(writer->write(integral_str.view())); 273 if (has_decimal_point) 274 RET_IF_RESULT_NEGATIVE(writer->write(DECIMAL_POINT)); 275 if (valid_fraction_digits > 0) 276 RET_IF_RESULT_NEGATIVE( 277 writer->write({fraction_digits, valid_fraction_digits})); 278 if (trailing_zeroes > 0) 279 RET_IF_RESULT_NEGATIVE(writer->write('0', trailing_zeroes)); 280 if (padding > 0) 281 RET_IF_RESULT_NEGATIVE(writer->write(' ', padding)); 282 } else { 283 // The pattern is (spaces), (sign), (zeroes), integral, (.), (fraction), 284 // (zeroes) 285 if ((padding > 0) && 286 ((flags & FormatFlags::LEADING_ZEROES) != FormatFlags::LEADING_ZEROES)) 287 RET_IF_RESULT_NEGATIVE(writer->write(' ', padding)); 288 if (sign_char > 0) 289 RET_IF_RESULT_NEGATIVE(writer->write(sign_char)); 290 if ((padding > 0) && 291 ((flags & FormatFlags::LEADING_ZEROES) == FormatFlags::LEADING_ZEROES)) 292 RET_IF_RESULT_NEGATIVE(writer->write('0', padding)); 293 RET_IF_RESULT_NEGATIVE(writer->write(integral_str.view())); 294 if (has_decimal_point) 295 RET_IF_RESULT_NEGATIVE(writer->write(DECIMAL_POINT)); 296 if (valid_fraction_digits > 0) 297 RET_IF_RESULT_NEGATIVE( 298 writer->write({fraction_digits, valid_fraction_digits})); 299 if (trailing_zeroes > 0) 300 RET_IF_RESULT_NEGATIVE(writer->write('0', trailing_zeroes)); 301 } 302 return WRITE_OK; 303 } 304 305 } // namespace printf_core 306 } // namespace LIBC_NAMESPACE_DECL 307 308 #endif // LLVM_LIBC_SRC_STDIO_PRINTF_CORE_FIXED_CONVERTER_H 309