1//===- FixedPoint.cpp - Fixed point constant handling -----------*- 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/// \file
10/// Defines the implementation for the fixed point number interface.
11//
12//===----------------------------------------------------------------------===//
13
14#include "clang/Basic/FixedPoint.h"
15
16namespace clang {
17
18APFixedPoint APFixedPoint::convert(const FixedPointSemantics &DstSema,
19                                   bool *Overflow) const {
20  llvm::APSInt NewVal = Val;
21  unsigned DstWidth = DstSema.getWidth();
22  unsigned DstScale = DstSema.getScale();
23  bool Upscaling = DstScale > getScale();
24  if (Overflow)
25    *Overflow = false;
26
27  if (Upscaling) {
28    NewVal = NewVal.extend(NewVal.getBitWidth() + DstScale - getScale());
29    NewVal <<= (DstScale - getScale());
30  } else {
31    NewVal >>= (getScale() - DstScale);
32  }
33
34  auto Mask = llvm::APInt::getBitsSetFrom(
35      NewVal.getBitWidth(),
36      std::min(DstScale + DstSema.getIntegralBits(), NewVal.getBitWidth()));
37  llvm::APInt Masked(NewVal & Mask);
38
39  // Change in the bits above the sign
40  if (!(Masked == Mask || Masked == 0)) {
41    // Found overflow in the bits above the sign
42    if (DstSema.isSaturated())
43      NewVal = NewVal.isNegative() ? Mask : ~Mask;
44    else if (Overflow)
45      *Overflow = true;
46  }
47
48  // If the dst semantics are unsigned, but our value is signed and negative, we
49  // clamp to zero.
50  if (!DstSema.isSigned() && NewVal.isSigned() && NewVal.isNegative()) {
51    // Found negative overflow for unsigned result
52    if (DstSema.isSaturated())
53      NewVal = 0;
54    else if (Overflow)
55      *Overflow = true;
56  }
57
58  NewVal = NewVal.extOrTrunc(DstWidth);
59  NewVal.setIsSigned(DstSema.isSigned());
60  return APFixedPoint(NewVal, DstSema);
61}
62
63int APFixedPoint::compare(const APFixedPoint &Other) const {
64  llvm::APSInt ThisVal = getValue();
65  llvm::APSInt OtherVal = Other.getValue();
66  bool ThisSigned = Val.isSigned();
67  bool OtherSigned = OtherVal.isSigned();
68  unsigned OtherScale = Other.getScale();
69  unsigned OtherWidth = OtherVal.getBitWidth();
70
71  unsigned CommonWidth = std::max(Val.getBitWidth(), OtherWidth);
72
73  // Prevent overflow in the event the widths are the same but the scales differ
74  CommonWidth += getScale() >= OtherScale ? getScale() - OtherScale
75                                          : OtherScale - getScale();
76
77  ThisVal = ThisVal.extOrTrunc(CommonWidth);
78  OtherVal = OtherVal.extOrTrunc(CommonWidth);
79
80  unsigned CommonScale = std::max(getScale(), OtherScale);
81  ThisVal = ThisVal.shl(CommonScale - getScale());
82  OtherVal = OtherVal.shl(CommonScale - OtherScale);
83
84  if (ThisSigned && OtherSigned) {
85    if (ThisVal.sgt(OtherVal))
86      return 1;
87    else if (ThisVal.slt(OtherVal))
88      return -1;
89  } else if (!ThisSigned && !OtherSigned) {
90    if (ThisVal.ugt(OtherVal))
91      return 1;
92    else if (ThisVal.ult(OtherVal))
93      return -1;
94  } else if (ThisSigned && !OtherSigned) {
95    if (ThisVal.isSignBitSet())
96      return -1;
97    else if (ThisVal.ugt(OtherVal))
98      return 1;
99    else if (ThisVal.ult(OtherVal))
100      return -1;
101  } else {
102    // !ThisSigned && OtherSigned
103    if (OtherVal.isSignBitSet())
104      return 1;
105    else if (ThisVal.ugt(OtherVal))
106      return 1;
107    else if (ThisVal.ult(OtherVal))
108      return -1;
109  }
110
111  return 0;
112}
113
114APFixedPoint APFixedPoint::getMax(const FixedPointSemantics &Sema) {
115  bool IsUnsigned = !Sema.isSigned();
116  auto Val = llvm::APSInt::getMaxValue(Sema.getWidth(), IsUnsigned);
117  if (IsUnsigned && Sema.hasUnsignedPadding())
118    Val = Val.lshr(1);
119  return APFixedPoint(Val, Sema);
120}
121
122APFixedPoint APFixedPoint::getMin(const FixedPointSemantics &Sema) {
123  auto Val = llvm::APSInt::getMinValue(Sema.getWidth(), !Sema.isSigned());
124  return APFixedPoint(Val, Sema);
125}
126
127FixedPointSemantics FixedPointSemantics::getCommonSemantics(
128    const FixedPointSemantics &Other) const {
129  unsigned CommonScale = std::max(getScale(), Other.getScale());
130  unsigned CommonWidth =
131      std::max(getIntegralBits(), Other.getIntegralBits()) + CommonScale;
132
133  bool ResultIsSigned = isSigned() || Other.isSigned();
134  bool ResultIsSaturated = isSaturated() || Other.isSaturated();
135  bool ResultHasUnsignedPadding = false;
136  if (!ResultIsSigned) {
137    // Both are unsigned.
138    ResultHasUnsignedPadding = hasUnsignedPadding() &&
139                               Other.hasUnsignedPadding() && !ResultIsSaturated;
140  }
141
142  // If the result is signed, add an extra bit for the sign. Otherwise, if it is
143  // unsigned and has unsigned padding, we only need to add the extra padding
144  // bit back if we are not saturating.
145  if (ResultIsSigned || ResultHasUnsignedPadding)
146    CommonWidth++;
147
148  return FixedPointSemantics(CommonWidth, CommonScale, ResultIsSigned,
149                             ResultIsSaturated, ResultHasUnsignedPadding);
150}
151
152APFixedPoint APFixedPoint::add(const APFixedPoint &Other,
153                               bool *Overflow) const {
154  auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
155  APFixedPoint ConvertedThis = convert(CommonFXSema);
156  APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
157  llvm::APSInt ThisVal = ConvertedThis.getValue();
158  llvm::APSInt OtherVal = ConvertedOther.getValue();
159  bool Overflowed = false;
160
161  llvm::APSInt Result;
162  if (CommonFXSema.isSaturated()) {
163    Result = CommonFXSema.isSigned() ? ThisVal.sadd_sat(OtherVal)
164                                     : ThisVal.uadd_sat(OtherVal);
165  } else {
166    Result = ThisVal.isSigned() ? ThisVal.sadd_ov(OtherVal, Overflowed)
167                                : ThisVal.uadd_ov(OtherVal, Overflowed);
168  }
169
170  if (Overflow)
171    *Overflow = Overflowed;
172
173  return APFixedPoint(Result, CommonFXSema);
174}
175
176APFixedPoint APFixedPoint::sub(const APFixedPoint &Other,
177                               bool *Overflow) const {
178  auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
179  APFixedPoint ConvertedThis = convert(CommonFXSema);
180  APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
181  llvm::APSInt ThisVal = ConvertedThis.getValue();
182  llvm::APSInt OtherVal = ConvertedOther.getValue();
183  bool Overflowed = false;
184
185  llvm::APSInt Result;
186  if (CommonFXSema.isSaturated()) {
187    Result = CommonFXSema.isSigned() ? ThisVal.ssub_sat(OtherVal)
188                                     : ThisVal.usub_sat(OtherVal);
189  } else {
190    Result = ThisVal.isSigned() ? ThisVal.ssub_ov(OtherVal, Overflowed)
191                                : ThisVal.usub_ov(OtherVal, Overflowed);
192  }
193
194  if (Overflow)
195    *Overflow = Overflowed;
196
197  return APFixedPoint(Result, CommonFXSema);
198}
199
200APFixedPoint APFixedPoint::mul(const APFixedPoint &Other,
201                               bool *Overflow) const {
202  auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
203  APFixedPoint ConvertedThis = convert(CommonFXSema);
204  APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
205  llvm::APSInt ThisVal = ConvertedThis.getValue();
206  llvm::APSInt OtherVal = ConvertedOther.getValue();
207  bool Overflowed = false;
208
209  // Widen the LHS and RHS so we can perform a full multiplication.
210  unsigned Wide = CommonFXSema.getWidth() * 2;
211  if (CommonFXSema.isSigned()) {
212    ThisVal = ThisVal.sextOrSelf(Wide);
213    OtherVal = OtherVal.sextOrSelf(Wide);
214  } else {
215    ThisVal = ThisVal.zextOrSelf(Wide);
216    OtherVal = OtherVal.zextOrSelf(Wide);
217  }
218
219  // Perform the full multiplication and downscale to get the same scale.
220  //
221  // Note that the right shifts here perform an implicit downwards rounding.
222  // This rounding could discard bits that would technically place the result
223  // outside the representable range. We interpret the spec as allowing us to
224  // perform the rounding step first, avoiding the overflow case that would
225  // arise.
226  llvm::APSInt Result;
227  if (CommonFXSema.isSigned())
228    Result = ThisVal.smul_ov(OtherVal, Overflowed)
229                    .ashr(CommonFXSema.getScale());
230  else
231    Result = ThisVal.umul_ov(OtherVal, Overflowed)
232                    .lshr(CommonFXSema.getScale());
233  assert(!Overflowed && "Full multiplication cannot overflow!");
234  Result.setIsSigned(CommonFXSema.isSigned());
235
236  // If our result lies outside of the representative range of the common
237  // semantic, we either have overflow or saturation.
238  llvm::APSInt Max = APFixedPoint::getMax(CommonFXSema).getValue()
239                                                       .extOrTrunc(Wide);
240  llvm::APSInt Min = APFixedPoint::getMin(CommonFXSema).getValue()
241                                                       .extOrTrunc(Wide);
242  if (CommonFXSema.isSaturated()) {
243    if (Result < Min)
244      Result = Min;
245    else if (Result > Max)
246      Result = Max;
247  } else
248    Overflowed = Result < Min || Result > Max;
249
250  if (Overflow)
251    *Overflow = Overflowed;
252
253  return APFixedPoint(Result.sextOrTrunc(CommonFXSema.getWidth()),
254                      CommonFXSema);
255}
256
257APFixedPoint APFixedPoint::div(const APFixedPoint &Other,
258                               bool *Overflow) const {
259  auto CommonFXSema = Sema.getCommonSemantics(Other.getSemantics());
260  APFixedPoint ConvertedThis = convert(CommonFXSema);
261  APFixedPoint ConvertedOther = Other.convert(CommonFXSema);
262  llvm::APSInt ThisVal = ConvertedThis.getValue();
263  llvm::APSInt OtherVal = ConvertedOther.getValue();
264  bool Overflowed = false;
265
266  // Widen the LHS and RHS so we can perform a full division.
267  unsigned Wide = CommonFXSema.getWidth() * 2;
268  if (CommonFXSema.isSigned()) {
269    ThisVal = ThisVal.sextOrSelf(Wide);
270    OtherVal = OtherVal.sextOrSelf(Wide);
271  } else {
272    ThisVal = ThisVal.zextOrSelf(Wide);
273    OtherVal = OtherVal.zextOrSelf(Wide);
274  }
275
276  // Upscale to compensate for the loss of precision from division, and
277  // perform the full division.
278  ThisVal = ThisVal.shl(CommonFXSema.getScale());
279  llvm::APSInt Result;
280  if (CommonFXSema.isSigned()) {
281    llvm::APInt Rem;
282    llvm::APInt::sdivrem(ThisVal, OtherVal, Result, Rem);
283    // If the quotient is negative and the remainder is nonzero, round
284    // towards negative infinity by subtracting epsilon from the result.
285    if (ThisVal.isNegative() != OtherVal.isNegative() && !Rem.isNullValue())
286      Result = Result - 1;
287  } else
288    Result = ThisVal.udiv(OtherVal);
289  Result.setIsSigned(CommonFXSema.isSigned());
290
291  // If our result lies outside of the representative range of the common
292  // semantic, we either have overflow or saturation.
293  llvm::APSInt Max = APFixedPoint::getMax(CommonFXSema).getValue()
294                                                       .extOrTrunc(Wide);
295  llvm::APSInt Min = APFixedPoint::getMin(CommonFXSema).getValue()
296                                                       .extOrTrunc(Wide);
297  if (CommonFXSema.isSaturated()) {
298    if (Result < Min)
299      Result = Min;
300    else if (Result > Max)
301      Result = Max;
302  } else
303    Overflowed = Result < Min || Result > Max;
304
305  if (Overflow)
306    *Overflow = Overflowed;
307
308  return APFixedPoint(Result.sextOrTrunc(CommonFXSema.getWidth()),
309                      CommonFXSema);
310}
311
312void APFixedPoint::toString(llvm::SmallVectorImpl<char> &Str) const {
313  llvm::APSInt Val = getValue();
314  unsigned Scale = getScale();
315
316  if (Val.isSigned() && Val.isNegative() && Val != -Val) {
317    Val = -Val;
318    Str.push_back('-');
319  }
320
321  llvm::APSInt IntPart = Val >> Scale;
322
323  // Add 4 digits to hold the value after multiplying 10 (the radix)
324  unsigned Width = Val.getBitWidth() + 4;
325  llvm::APInt FractPart = Val.zextOrTrunc(Scale).zext(Width);
326  llvm::APInt FractPartMask = llvm::APInt::getAllOnesValue(Scale).zext(Width);
327  llvm::APInt RadixInt = llvm::APInt(Width, 10);
328
329  IntPart.toString(Str, /*Radix=*/10);
330  Str.push_back('.');
331  do {
332    (FractPart * RadixInt)
333        .lshr(Scale)
334        .toString(Str, /*Radix=*/10, Val.isSigned());
335    FractPart = (FractPart * RadixInt) & FractPartMask;
336  } while (FractPart != 0);
337}
338
339APFixedPoint APFixedPoint::negate(bool *Overflow) const {
340  if (!isSaturated()) {
341    if (Overflow)
342      *Overflow =
343          (!isSigned() && Val != 0) || (isSigned() && Val.isMinSignedValue());
344    return APFixedPoint(-Val, Sema);
345  }
346
347  // We never overflow for saturation
348  if (Overflow)
349    *Overflow = false;
350
351  if (isSigned())
352    return Val.isMinSignedValue() ? getMax(Sema) : APFixedPoint(-Val, Sema);
353  else
354    return APFixedPoint(Sema);
355}
356
357llvm::APSInt APFixedPoint::convertToInt(unsigned DstWidth, bool DstSign,
358                                        bool *Overflow) const {
359  llvm::APSInt Result = getIntPart();
360  unsigned SrcWidth = getWidth();
361
362  llvm::APSInt DstMin = llvm::APSInt::getMinValue(DstWidth, !DstSign);
363  llvm::APSInt DstMax = llvm::APSInt::getMaxValue(DstWidth, !DstSign);
364
365  if (SrcWidth < DstWidth) {
366    Result = Result.extend(DstWidth);
367  } else if (SrcWidth > DstWidth) {
368    DstMin = DstMin.extend(SrcWidth);
369    DstMax = DstMax.extend(SrcWidth);
370  }
371
372  if (Overflow) {
373    if (Result.isSigned() && !DstSign) {
374      *Overflow = Result.isNegative() || Result.ugt(DstMax);
375    } else if (Result.isUnsigned() && DstSign) {
376      *Overflow = Result.ugt(DstMax);
377    } else {
378      *Overflow = Result < DstMin || Result > DstMax;
379    }
380  }
381
382  Result.setIsSigned(DstSign);
383  return Result.extOrTrunc(DstWidth);
384}
385
386APFixedPoint APFixedPoint::getFromIntValue(const llvm::APSInt &Value,
387                                           const FixedPointSemantics &DstFXSema,
388                                           bool *Overflow) {
389  FixedPointSemantics IntFXSema = FixedPointSemantics::GetIntegerSemantics(
390      Value.getBitWidth(), Value.isSigned());
391  return APFixedPoint(Value, IntFXSema).convert(DstFXSema, Overflow);
392}
393
394}  // namespace clang
395