xorn/src/python/hybridnum.py

   1 # Copyright (C) 2013-2020 Roland Lutz
   2 #
   3 # This program is free software; you can redistribute it and/or modify
   4 # it under the terms of the GNU General Public License as published by
   5 # the Free Software Foundation; either version 2 of the License, or
   6 # (at your option) any later version.
   7 #
   8 # This program is distributed in the hope that it will be useful,
   9 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11 # GNU General Public License for more details.
  12 #
  13 # You should have received a copy of the GNU General Public License
  14 # along with this program; if not, write to the Free Software Foundation,
  15 # Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  16
  17 ## \namespace xorn.hybridnum
  18 ## Hybrid fixed-/floating-point numbers.
  19 #
  20 # This module provides formatting and parsing functions for a hybrid
  21 # number format which uses floating-point numbers as the base of a
  22 # fixed-point notation.  This way, decimal fractions down to an
  23 # arbitrary (but fixed) number of digits can be represented exactly
  24 # while still allowing the benefits from a floating-point number
  25 # format.
  26 #
  27 # As an example, in a format with three fixed digits, both the number
  28 # \c 1 (represented as the floating-point value \c 1000.0) and the
  29 # number \c 0.001 (represented as the floating-point value \c 1.0) can
  30 # be represented exactly, whereas the number \c 0.0001 (represented as
  31 # the floating-point number \c 0.1) would be subject to conversion
  32 # errors.
  33 #
  34 # To avoid the usual errors when converting a floating-point number to
  35 # a string and vice versa, hexadecimal notation is used for the
  36 # decimals to the floating-point representation.
  37
  38 ## Convert a floating-point number to its hybrid string representation.
  39 #
  40 # TODO: For efficiency reasons, this should probably be ported to C.
  41
  42 def format(x, decimal_digits):
  43     if not isinstance(decimal_digits, int):
  44         raise TypeError, 'number of decimals must be an integer'
  45     if decimal_digits < 0:
  46         raise ValueError, 'number of decimals must be non-negative'
  47
  48     s = float(x).hex()
  49
  50     if s[0] == '-':
  51         sign = '-'
  52         s = s[1:]
  53     else:
  54         sign = ''
  55
  56     assert s[0] == '0' and s[1] == 'x'
  57     s = s[2:]
  58
  59     pos = s.index('p')
  60     assert s[pos + 1] == '+' or s[pos + 1] == '-'
  61     mant, exp = s[:pos], int(s[pos + 1:])
  62
  63     bits = []
  64     if mant[0] == '0':
  65         bits.append(0)  # shouldn't normally happen, though
  66     elif mant[0] == '1':
  67         bits.append(1)
  68     else:
  69         raise AssertionError
  70     assert mant[1] == '.'
  71     for c in mant[2:]:
  72         d = int(c, 16)
  73         bits.append((d >> 3) & 1)
  74         bits.append((d >> 2) & 1)
  75         bits.append((d >> 1) & 1)
  76         bits.append((d >> 0) & 1)
  77
  78     if exp < 0:
  79         bits_before = []
  80         bits_after = [0] * -(exp + 1) + bits
  81     else:
  82         while len(bits) < exp + 1:
  83             bits.append(0)
  84         bits_before = bits[:exp + 1]
  85         bits_after = bits[exp + 1:]
  86
  87     while bits_after and bits_after[-1] == 0:
  88         del bits_after[-1]
  89     while len(bits_after) % 4 != 0:
  90         bits_after.append(0)
  91
  92     before = str(sum(b << i for i, b in enumerate(reversed(bits_before))))
  93     after = ''
  94     for i in xrange(0, len(bits_after), 4):
  95         after += '0123456789abcdef'[(bits_after[i] << 3) +
  96                                     (bits_after[i + 1] << 2) +
  97                                     (bits_after[i + 2] << 1) +
  98                                      bits_after[i + 3]]
  99
 100     if decimal_digits == 0:
 101         if after:
 102             if before == '0':
 103                 return sign + ':' + after
 104             return sign + before + ':' + after
 105         if before == '0':
 106             return '0'  # signless zero
 107         return sign + before
 108
 109     if len(before) < decimal_digits:
 110         before = '0' * (decimal_digits - len(before)) + before
 111     before0 = before[:-decimal_digits]
 112     before1 = before[-decimal_digits:]
 113
 114     if before1 == '0' * decimal_digits:
 115         if after:
 116             if not before0:
 117                 return sign + ':' + after
 118             return sign + before0 + '.' + before1 + ':' + after
 119         else:
 120             if not before0:
 121                 return '0'  # signless zero
 122             return sign + before0
 123     else:
 124         if after:
 125             return sign + before0 + '.' + before1 + ':' + after
 126         else:
 127             return sign + before0 + '.' + before1.rstrip('0')
 128
 129 ## Convert a hybrid string representation to a floating-point number.
 130 #
 131 # TODO: For efficiency reasons, this should probably be ported to C.
 132
 133 def parse(s, decimal_digits):
 134     if not isinstance(s, str) and not isinstance(s, unicode):
 135         raise TypeError, 'invalid argument type (must be str or unicode)'
 136     if not isinstance(decimal_digits, int):
 137         raise TypeError, 'number of decimals must be an integer'
 138     if decimal_digits < 0:
 139         raise ValueError, 'number of decimals must be non-negative'
 140
 141     if s and s[0] == '-':
 142         sign = -1
 143         s = s[1:]
 144     else:
 145         sign = 1
 146
 147     try:
 148         pos = s.index(':')
 149     except ValueError:
 150         after = None
 151         if not s:
 152             raise ValueError
 153     else:
 154         after = s[pos + 1:]
 155         s = s[:pos]
 156         if not after and not s:
 157             raise ValueError
 158
 159     if decimal_digits == 0:
 160         if '.' in s:
 161             raise ValueError
 162         before0 = s
 163         before1 = ''
 164     else:
 165         try:
 166             pos = s.index('.')
 167         except ValueError:
 168             if s and after is not None:
 169                 raise ValueError
 170             before0 = s
 171             before1 = ''
 172         else:
 173             before0 = s[:pos]
 174             before1 = s[pos + 1:]
 175             if not before0 and not before1:
 176                 raise ValueError
 177             if len(before1) < decimal_digits:
 178                 if after is not None:
 179                     raise ValueError
 180                 before1 = before1 + (decimal_digits - len(before1)) * '0'
 181
 182         if len(before1) > decimal_digits:
 183             raise ValueError
 184
 185     if not after:
 186         after = '0'
 187
 188     for c in before0 + before1:
 189         if c not in '0123456789':
 190             raise ValueError
 191     for c in after:
 192         if c not in '0123456789abcdef':
 193             raise ValueError
 194
 195     if not before0:
 196         before0 = '0'
 197     if not before1:
 198         before1 = '0'
 199
 200     x = float(int(before0) * 10 ** decimal_digits + int(before1)) + \
 201         float(int(after, 16)) / float(1 << len(after) * 4)
 202
 203     if not x:
 204         return 0.  # signless zero
 205     return sign * x