311 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef LLVM_LIBC_SRC_STDIO_PRINTF_CORE_FIXED_CONVERTER_H10#define LLVM_LIBC_SRC_STDIO_PRINTF_CORE_FIXED_CONVERTER_H11 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 27namespace LIBC_NAMESPACE_DECL {28namespace printf_core {29 30// This is just for assertions. It will be compiled out for release builds.31LIBC_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 66template <WriteMode write_mode>67LIBC_INLINE int convert_fixed(Writer<write_mode> *writer,68 const FormatSection &to_conv) {69 // Long accum should be the largest type, so we can store all the smaller70 // numbers in things sized for it.71 using LARep = fixed_point::FXRep<unsigned long accum>;72 using StorageType = LARep::StorageType;73 74 FormatFlags flags = to_conv.flags;75 76 bool is_negative;77 int exponent;78 StorageType integral;79 StorageType fractional;80 81 // r = fract82 // k = accum83 // lowercase = signed84 // uppercase = unsigned85 // h = short86 // l = long87 // any other length modifier has no effect88 89 if (to_conv.length_modifier == LengthModifier::h) {90 APPLY_FX_LENGTH_MODIFIER(short);91 } else if (to_conv.length_modifier == LengthModifier::l) {92 APPLY_FX_LENGTH_MODIFIER(long);93 } else {94 APPLY_FX_LENGTH_MODIFIER();95 }96 97 LIBC_ASSERT(static_cast<size_t>(exponent) <=98 (sizeof(StorageType) - sizeof(uint32_t)) * CHAR_BIT &&99 "StorageType must be large enough to hold the fractional "100 "component multiplied by a 32 bit number.");101 102 // If to_conv doesn't specify a precision, the precision defaults to 6.103 const size_t precision = to_conv.precision < 0 ? 6 : to_conv.precision;104 bool has_decimal_point =105 (precision > 0) || ((flags & FormatFlags::ALTERNATE_FORM) != 0);106 107 // The number of non-zero digits below the decimal point for a negative power108 // of 2 in base 10 is equal to the magnitude of the power of 2.109 110 // A quick proof:111 // Let p be any positive integer.112 // Let e = 2^(-p)113 // Let t be a positive integer such that e * 10^t is an integer.114 // By definition: The smallest allowed value of t must be equal to the number115 // of non-zero digits below the decimal point in e.116 // If we evaluate e * 10^t we get the following:117 // e * 10^t = 2^(-p) * 10*t = 2^(-p) * 2^t * 5^t = 5^t * 2^(t-p)118 // For 5^t * 2^(t-p) to be an integer, both exponents must be non-negative,119 // since 5 and 2 are coprime.120 // The smallest value of t such that t-p is non-negative is p.121 // Therefor, the number of non-zero digits below the decimal point for a given122 // negative power of 2 "p" is equal to the value of p.123 124 constexpr size_t MAX_FRACTION_DIGITS = LARep::FRACTION_LEN;125 126 char fraction_digits[MAX_FRACTION_DIGITS];127 128 size_t valid_fraction_digits = 0;129 130 // TODO: Factor this part out131 while (fractional > 0) {132 uint32_t cur_digits = 0;133 // 10^9 is used since it's the largest power of 10 that fits in a uint32_t134 constexpr uint32_t TEN_EXP_NINE = 1000000000;135 constexpr size_t DIGITS_PER_BLOCK = 9;136 137 // Multiply by 10^9, then grab the digits above the decimal point, then138 // clear those digits in fractional.139 fractional = fractional * TEN_EXP_NINE;140 cur_digits = static_cast<uint32_t>(fractional >> exponent);141 fractional = fractional % (StorageType(1) << exponent);142 143 // we add TEN_EXP_NINE to force leading zeroes to show up, then we skip the144 // first digit in the loop.145 const IntegerToString<uint32_t> cur_fractional_digits(cur_digits +146 TEN_EXP_NINE);147 for (size_t i = 0;148 i < DIGITS_PER_BLOCK && valid_fraction_digits < MAX_FRACTION_DIGITS;149 ++i, ++valid_fraction_digits)150 fraction_digits[valid_fraction_digits] =151 cur_fractional_digits.view()[i + 1];152 153 if (valid_fraction_digits >= MAX_FRACTION_DIGITS) {154 LIBC_ASSERT(fractional == 0 && "If the fraction digit buffer is full, "155 "there should be no remaining digits.");156 /*157 A visual explanation of what this assert is checking:158 159 32 digits (max for 32 bit fract)160 +------------------------------++--+--- must be zero161 | || |162 123456789012345678901234567890120000163 | || || || |164 +-------++-------++-------++-------+165 9 digit blocks166 */167 LIBC_ASSERT(cur_digits % const_ten_exp(168 DIGITS_PER_BLOCK -169 (MAX_FRACTION_DIGITS % DIGITS_PER_BLOCK)) ==170 0 &&171 "Digits after the MAX_FRACTION_DIGITS should all be zero.");172 valid_fraction_digits = MAX_FRACTION_DIGITS;173 }174 }175 176 if (precision < valid_fraction_digits) {177 // Handle rounding. Just do round to nearest, tie to even since it's178 // unspecified.179 RoundDirection round;180 char first_digit_after = fraction_digits[precision];181 if (internal::b36_char_to_int(first_digit_after) > 5) {182 round = RoundDirection::Up;183 } else if (internal::b36_char_to_int(first_digit_after) < 5) {184 round = RoundDirection::Down;185 } else {186 // first_digit_after == '5'187 // need to check the remaining digits, but default to even.188 round = RoundDirection::Even;189 for (size_t cur_digit_index = precision + 1;190 cur_digit_index + 1 < valid_fraction_digits; ++cur_digit_index) {191 if (fraction_digits[cur_digit_index] != '0') {192 round = RoundDirection::Up;193 break;194 }195 }196 }197 198 // If we need to actually perform rounding, do so.199 if (round == RoundDirection::Up || round == RoundDirection::Even) {200 bool keep_rounding = true;201 int digit_to_round = static_cast<int>(precision) - 1;202 for (; digit_to_round >= 0 && keep_rounding; --digit_to_round) {203 keep_rounding = false;204 char cur_digit = fraction_digits[digit_to_round];205 // if the digit should not be rounded up206 if (round == RoundDirection::Even &&207 (internal::b36_char_to_int(cur_digit) % 2) == 0) {208 // break out of the loop209 break;210 }211 fraction_digits[digit_to_round] += 1;212 213 // if the digit was a 9, instead replace with a 0.214 if (cur_digit == '9') {215 fraction_digits[digit_to_round] = '0';216 keep_rounding = true;217 }218 }219 220 // if every digit below the decimal point was rounded up but we need to221 // keep rounding222 if (keep_rounding &&223 (round == RoundDirection::Up ||224 (round == RoundDirection::Even && ((integral % 2) == 1)))) {225 // add one to the integral portion to round it up.226 ++integral;227 }228 }229 230 valid_fraction_digits = precision;231 }232 233 const IntegerToString<StorageType> integral_str(integral);234 235 // these are signed to prevent underflow due to negative values. The236 // eventual values will always be non-negative.237 size_t trailing_zeroes = 0;238 int padding;239 240 // If the precision is greater than the actual result, pad with 0s241 if (precision > valid_fraction_digits)242 trailing_zeroes = precision - (valid_fraction_digits);243 244 constexpr cpp::string_view DECIMAL_POINT(".");245 246 char sign_char = 0;247 248 // Check if the conv name is uppercase249 if (internal::isupper(to_conv.conv_name)) {250 // These flags are only for signed conversions, so this removes them if the251 // conversion is unsigned.252 flags = FormatFlags(flags &253 ~(FormatFlags::FORCE_SIGN | FormatFlags::SPACE_PREFIX));254 }255 256 if (is_negative)257 sign_char = '-';258 else if ((flags & FormatFlags::FORCE_SIGN) == FormatFlags::FORCE_SIGN)259 sign_char = '+'; // FORCE_SIGN has precedence over SPACE_PREFIX260 else if ((flags & FormatFlags::SPACE_PREFIX) == FormatFlags::SPACE_PREFIX)261 sign_char = ' ';262 263 padding = static_cast<int>(to_conv.min_width - (sign_char > 0 ? 1 : 0) -264 integral_str.size() -265 static_cast<int>(has_decimal_point) -266 valid_fraction_digits - trailing_zeroes);267 if (padding < 0)268 padding = 0;269 270 if ((flags & FormatFlags::LEFT_JUSTIFIED) == FormatFlags::LEFT_JUSTIFIED) {271 // The pattern is (sign), integral, (.), (fraction), (zeroes), (spaces)272 if (sign_char > 0)273 RET_IF_RESULT_NEGATIVE(writer->write(sign_char));274 RET_IF_RESULT_NEGATIVE(writer->write(integral_str.view()));275 if (has_decimal_point)276 RET_IF_RESULT_NEGATIVE(writer->write(DECIMAL_POINT));277 if (valid_fraction_digits > 0)278 RET_IF_RESULT_NEGATIVE(279 writer->write({fraction_digits, valid_fraction_digits}));280 if (trailing_zeroes > 0)281 RET_IF_RESULT_NEGATIVE(writer->write('0', trailing_zeroes));282 if (padding > 0)283 RET_IF_RESULT_NEGATIVE(writer->write(' ', padding));284 } else {285 // The pattern is (spaces), (sign), (zeroes), integral, (.), (fraction),286 // (zeroes)287 if ((padding > 0) &&288 ((flags & FormatFlags::LEADING_ZEROES) != FormatFlags::LEADING_ZEROES))289 RET_IF_RESULT_NEGATIVE(writer->write(' ', padding));290 if (sign_char > 0)291 RET_IF_RESULT_NEGATIVE(writer->write(sign_char));292 if ((padding > 0) &&293 ((flags & FormatFlags::LEADING_ZEROES) == FormatFlags::LEADING_ZEROES))294 RET_IF_RESULT_NEGATIVE(writer->write('0', padding));295 RET_IF_RESULT_NEGATIVE(writer->write(integral_str.view()));296 if (has_decimal_point)297 RET_IF_RESULT_NEGATIVE(writer->write(DECIMAL_POINT));298 if (valid_fraction_digits > 0)299 RET_IF_RESULT_NEGATIVE(300 writer->write({fraction_digits, valid_fraction_digits}));301 if (trailing_zeroes > 0)302 RET_IF_RESULT_NEGATIVE(writer->write('0', trailing_zeroes));303 }304 return WRITE_OK;305}306 307} // namespace printf_core308} // namespace LIBC_NAMESPACE_DECL309 310#endif // LLVM_LIBC_SRC_STDIO_PRINTF_CORE_FIXED_CONVERTER_H311