1 //===- APFixedPoint.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 "llvm/ADT/APFixedPoint.h"
15 
16 namespace llvm {
17 
18 APFixedPoint APFixedPoint::convert(const FixedPointSemantics &DstSema,
19                                    bool *Overflow) const {
20   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 = APInt::getBitsSetFrom(
35       NewVal.getBitWidth(),
36       std::min(DstScale + DstSema.getIntegralBits(), NewVal.getBitWidth()));
37   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 
63 int APFixedPoint::compare(const APFixedPoint &Other) const {
64   APSInt ThisVal = getValue();
65   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 
114 APFixedPoint APFixedPoint::getMax(const FixedPointSemantics &Sema) {
115   bool IsUnsigned = !Sema.isSigned();
116   auto Val = APSInt::getMaxValue(Sema.getWidth(), IsUnsigned);
117   if (IsUnsigned && Sema.hasUnsignedPadding())
118     Val = Val.lshr(1);
119   return APFixedPoint(Val, Sema);
120 }
121 
122 APFixedPoint APFixedPoint::getMin(const FixedPointSemantics &Sema) {
123   auto Val = APSInt::getMinValue(Sema.getWidth(), !Sema.isSigned());
124   return APFixedPoint(Val, Sema);
125 }
126 
127 FixedPointSemantics 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 
152 APFixedPoint 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   APSInt ThisVal = ConvertedThis.getValue();
158   APSInt OtherVal = ConvertedOther.getValue();
159   bool Overflowed = false;
160 
161   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 
176 APFixedPoint 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   APSInt ThisVal = ConvertedThis.getValue();
182   APSInt OtherVal = ConvertedOther.getValue();
183   bool Overflowed = false;
184 
185   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 
200 APFixedPoint 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   APSInt ThisVal = ConvertedThis.getValue();
206   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   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   APSInt Max = APFixedPoint::getMax(CommonFXSema).getValue()
239                                                  .extOrTrunc(Wide);
240   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 
257 APFixedPoint 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   APSInt ThisVal = ConvertedThis.getValue();
263   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   APSInt Result;
280   if (CommonFXSema.isSigned()) {
281     APInt Rem;
282     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   APSInt Max = APFixedPoint::getMax(CommonFXSema).getValue()
294                                                  .extOrTrunc(Wide);
295   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 
312 APFixedPoint APFixedPoint::shl(unsigned Amt, bool *Overflow) const {
313   APSInt ThisVal = Val;
314   bool Overflowed = false;
315 
316   // Widen the LHS.
317   unsigned Wide = Sema.getWidth() * 2;
318   if (Sema.isSigned())
319     ThisVal = ThisVal.sextOrSelf(Wide);
320   else
321     ThisVal = ThisVal.zextOrSelf(Wide);
322 
323   // Clamp the shift amount at the original width, and perform the shift.
324   Amt = std::min(Amt, ThisVal.getBitWidth());
325   APSInt Result = ThisVal << Amt;
326   Result.setIsSigned(Sema.isSigned());
327 
328   // If our result lies outside of the representative range of the
329   // semantic, we either have overflow or saturation.
330   APSInt Max = APFixedPoint::getMax(Sema).getValue().extOrTrunc(Wide);
331   APSInt Min = APFixedPoint::getMin(Sema).getValue().extOrTrunc(Wide);
332   if (Sema.isSaturated()) {
333     if (Result < Min)
334       Result = Min;
335     else if (Result > Max)
336       Result = Max;
337   } else
338     Overflowed = Result < Min || Result > Max;
339 
340   if (Overflow)
341     *Overflow = Overflowed;
342 
343   return APFixedPoint(Result.sextOrTrunc(Sema.getWidth()), Sema);
344 }
345 
346 void APFixedPoint::toString(SmallVectorImpl<char> &Str) const {
347   APSInt Val = getValue();
348   unsigned Scale = getScale();
349 
350   if (Val.isSigned() && Val.isNegative() && Val != -Val) {
351     Val = -Val;
352     Str.push_back('-');
353   }
354 
355   APSInt IntPart = Val >> Scale;
356 
357   // Add 4 digits to hold the value after multiplying 10 (the radix)
358   unsigned Width = Val.getBitWidth() + 4;
359   APInt FractPart = Val.zextOrTrunc(Scale).zext(Width);
360   APInt FractPartMask = APInt::getAllOnesValue(Scale).zext(Width);
361   APInt RadixInt = APInt(Width, 10);
362 
363   IntPart.toString(Str, /*Radix=*/10);
364   Str.push_back('.');
365   do {
366     (FractPart * RadixInt)
367         .lshr(Scale)
368         .toString(Str, /*Radix=*/10, Val.isSigned());
369     FractPart = (FractPart * RadixInt) & FractPartMask;
370   } while (FractPart != 0);
371 }
372 
373 APFixedPoint APFixedPoint::negate(bool *Overflow) const {
374   if (!isSaturated()) {
375     if (Overflow)
376       *Overflow =
377           (!isSigned() && Val != 0) || (isSigned() && Val.isMinSignedValue());
378     return APFixedPoint(-Val, Sema);
379   }
380 
381   // We never overflow for saturation
382   if (Overflow)
383     *Overflow = false;
384 
385   if (isSigned())
386     return Val.isMinSignedValue() ? getMax(Sema) : APFixedPoint(-Val, Sema);
387   else
388     return APFixedPoint(Sema);
389 }
390 
391 APSInt APFixedPoint::convertToInt(unsigned DstWidth, bool DstSign,
392                                   bool *Overflow) const {
393   APSInt Result = getIntPart();
394   unsigned SrcWidth = getWidth();
395 
396   APSInt DstMin = APSInt::getMinValue(DstWidth, !DstSign);
397   APSInt DstMax = APSInt::getMaxValue(DstWidth, !DstSign);
398 
399   if (SrcWidth < DstWidth) {
400     Result = Result.extend(DstWidth);
401   } else if (SrcWidth > DstWidth) {
402     DstMin = DstMin.extend(SrcWidth);
403     DstMax = DstMax.extend(SrcWidth);
404   }
405 
406   if (Overflow) {
407     if (Result.isSigned() && !DstSign) {
408       *Overflow = Result.isNegative() || Result.ugt(DstMax);
409     } else if (Result.isUnsigned() && DstSign) {
410       *Overflow = Result.ugt(DstMax);
411     } else {
412       *Overflow = Result < DstMin || Result > DstMax;
413     }
414   }
415 
416   Result.setIsSigned(DstSign);
417   return Result.extOrTrunc(DstWidth);
418 }
419 
420 APFixedPoint APFixedPoint::getFromIntValue(const APSInt &Value,
421                                            const FixedPointSemantics &DstFXSema,
422                                            bool *Overflow) {
423   FixedPointSemantics IntFXSema = FixedPointSemantics::GetIntegerSemantics(
424       Value.getBitWidth(), Value.isSigned());
425   return APFixedPoint(Value, IntFXSema).convert(DstFXSema, Overflow);
426 }
427 
428 }  // namespace clang
429