# TWOSCOMPLEMENT with Large Numbers...
#
# Kermit macros to convert signed decimal numbers to two's complement
# hexadecimal notation and vice versa:
#
# DECTOHEX d n
#   Converts the decimal argument d to n-bit two's complement hex format;
#   n should be 4, 8, 16, 32, 64, or 128.
#   Example: "DECTOHEX -1 32" returns "FFFFFFFF".
#
# HEXTODEC h
#   Converts the hexadececimal two's-complement argument to signed decimal. 
#   Example: "HEXTODEC FFFFFFFF" returns "-1".
#
# This version does the big calculations with strings, rather than machine
# integers, so is able (in principle) to handle integers of any size.  As
# written it accommodates word sizes of 4, 8, 16, 32, 64, and 128.  The main
# application is on 32-bit hardware or Kermit versions (notably K95) built
# with 32-bit memory models when it is necessary to do decimal/hexadecimal
# conversions of larger numbers.  Since this version uses strings and not
# built-in machine arithmetic, it is considerably slower than the
# straightforward version would be, but still tolerable on modern hardware.
#
# Requires C-Kermit 8.0 or later or Kermit 95 2.0 or later.
#
# Search terms:
#   BIGNUM decimal/hexadecimal format conversion macro implementation;
#   string arithmetic; manipulation of large numbers as strings.
#   Decimal/binary conversion of big numbers.
# 
# F. da Cruz, Columbia University, Dec 2007 - Jan 2008
# Last update: Wed Jan  9 12:21:06 2008

# Largest positive integer for the supported word sizes

.maxint<4> = 7
.maxint<8> = 127
.maxint<16> = 32767
.maxint<32> = 2147483647
.maxint<64> = 9223372036854775807
.maxint<128> = 340282366920938463463374607431768211455

# Ditto plus one (because we can't necessarily do arithmetic on big numbers)

.maxplusone<4> = 8
.maxplusone<8> = 128
.maxplusone<16> = 32768
.maxplusone<32> = 2147483648
.maxplusone<64> = 9223372036854775808
.maxplusone<128> = 340282366920938463463374607431768211456

# Powers of 16 up to 32 (128 bits)

def POWEROF16 {  # This is a macro to keep the array private.
    local &p
    dcl \&p[] = 16 -
     256 -
     4096 -
     65536 -
     1048576 -
     16777216 -
     268435456 -
     4294967296 -
     68719476736 -
     1099511627776 -
     17592186044416 -
     281474976710656 -
     4503599627370496 -
     72057594037927936 -
     1152921504606846976 -
     18446744073709551616 -
     295147905179352825856 -
     4722366482869645213696 -
     75557863725914323419136 -
     1208925819614629174706176 -
     19342813113834066795298816 -
     309485009821345068724781056 -
     4951760157141521099596496896 -
     79228162514264337593543950336 -
     1267650600228229401496703205376 -
     20282409603651670423947251286016 -
     324518553658426726783156020576256 -
     5192296858534827628530496329220096 -
     83076749736557242056487941267521536 -
     1329227995784915872903807060280344576 -
     21267647932558653966460912964485513216 -
     340282366920938463463374607431768211456
    .\&p[0] = 1 # Because initialers start at 1.
    if not integer \%1 end 1 "\%0: NON-NUMERIC ARGUMENT '%1'"
    if ( < \%1 0 || > \%1  32 ) \%1 end 1 "\%0: ARGUMENT OUT OF RANGE '\%1'"
    return \&p[\%1]
}

# Macro BINTOHEX converts a binary string to hex.
#   \%1 = binary string to be converted
#   \%2 = word size in bits
#   Returns hex string
#
define BINTOHEX {
    undef \%6                                # Result accumulator
    .\%1 := \flpad(\%1,\%2,0)                # Pad to size if necessary
    for \%9 1 \%2 4 {                        # Do four bits at at a time
        .\%8 := \fsubstr(\%1,\%9,4)          # Get chunk of 4
        if not def \%8 break                 # Make sure we have one
        .\%7 := \fradix(\%8,2,16)            # Convert to Hex digit
        .\%6 := \%6\%7                       # Accumulate
    }
    return \%6
}

# HEXTOBIN converts hex string to binary
define HEXTOBIN {
    undef \%7
    for \%9 1 \flen(\%1) 1 {
        .\%7 := \%7\flpad(\fradix(\:(\%1[\%9:1]),16,2),4,0)
    }
    return \%7
}

# Macro DTOB converts a decimal string to binary.
#  \%1 = decimal string to be converted
#  Returns binary string
#
def DTOB {                                   # Convert decimal string to binary
    local div2 result remainder
    def DIV2 {                               # Divide decimal string by two
        local \%i
        undef \%6 \%7 result
        for \%i 1 \flen(\%1) 1 {             # One digit at a time.
            .\%9 := \%7\:(\%1[\%i:1])        # Get a digit.
            .\%8 ::= \%9/2                   # Divide it by 2
            .\%7 ::= \%9%2                   # Get remainder
            .\%6 := \%6\%8                   # Accumulate result
        }
        .result := \%6                       # These are just
        .remainder := \%7                    # for clarity...
    }
    while true {                             # Convert by repetitive division.
        div2 \%1                             # Divide decimal number by 2
        .\%6 := \m(remainder)\%6             # Accumulate result...
        .\%1 := \m(result)
        if not \fverify(0,\%1) break         # Quit when there's nothing left.
    }
    return \%6
}

# Macro TWOSCOMPLEMENT converts binary string into its two's complement
#  \%1 = binary string
#  \%2 = number of bits (if not given, length of \%1 is used)
#  Returns the 2's complement of the given binary string
#
define TWOSCOMPLEMENT {
    if not def \%2 .\%2 = \flen(\%1)         # Supply length if not given
    .\%9 := \flpad(\%1,\%2,0) }              # Left-pad to desired length
    .\%8 ::= \frindex(1,\%9) - 1             # Find first 1 from the right
    if == \%8 -1 return \frepeat(0,\%2 / 4)  # Watch out for negative 0
    .\%7 := \fsubstr(\%9,1,\%8)              # Split string here
    .\%6 := \fsubstitute(\%7,01,10)          # Complement bits in left part
    .\%5 := \%6\fsubstr(\%9,\%8+1)           # Put back with right part
    return \%5
}

# Macro DECTOHEX converts a signed decimal number to 2's complement hexadecimal
# using the macros defined above as workers.
#   \%1 = decimal number string (default 0)
#   \%2 = word size in bits
#         (must be a power of two, 4 or greater, default 32, max 128)
#   Returns the hex result of the requested size.
#
define DECTOHEX {
    local digits legal
    .legal = :4:8:16:32:64:128:              # Legal word sizes for dec-to-hex
    if not def \%1 .\%1 = 0                  # Supply default if no arg given
    if not numeric \%1 return NOT_A_NUMBER:\%1  # Check that arg is a number
    if not def \%2 .\%2 := 32                   # Use 32 bits if no second arg
    if not \findex(:\%2:,\m(legal)) end 1 "UNSUPPORTED WORD SIZE - \%2"
    .digits := \flen(\m(maxint<\%2>))           # Number of digits in it

    if eq "\fsubstr(\%1,1,1)" "+" .\%1 := \fsubstr(\%1,2) # strip any + sign
    if not eq "\fsubstr(\%1,1,1)" "-" {      # If argument is not signed...
        if lgt \flpad(\%1,\m(digits),0) \m(maxint<\%2>) return OVERFLOW
        dtob \%1                             # Convert from decimal to binary
        bintohex \v(return) \%2              # And from binary to hex
        return \flpad(\v(return),(\%2/4),0)  # Return padded result
    }
    .\%1 := \fsubstr(\%1,2)                  # Negative number - remove sign
    .\%1 := \flpad(\%1,\flen(\m(maxint<\%2>)),0) # Must use lexical comparison
    if llt \m(maxplusone<\%2>) \%1 return UNDERFLOW # Check magnitude
    dtob \%1                                 # Convert to binary
    .\%5 := \fexec(twoscomplement \v(return) \%2) # Get two's complement
    .\%4 := \fexec(bintohex \%5 \%2)         # Convert to hex
    return \%4
}

# IS32BIT checks if positive number fits in 32 bits.
# Could be used for optimization but not worth it.
#
def IS32BIT {
    .\%1 := \flpad(\ftrim(\%1,0),10,0)
    if lgt \%1 2147483647 return 0
    return 1
}

# Macro DECIMALADD adds two unsigned decimal strings regardless of magnitude.
# \%1, \%2 are decimal strings.
# Returns sum as decimal string.
#
def DECIMALADD {
    local \%s \%c
    .\%9 := \fmax(\flen(\%1),\flen(\%2))       # Get length of longest arg
    .\%1 := \flpad(\%1,\%9,0)                  # Pad both to same length
    .\%2 := \flpad(\%2,\%9,0)
    .\%c = 0                                   # Carry
    undef \%s                                  # Sum accumulator
    for \%9 \flen(\%1) 1 -1 {                  # Loop through digits RTL
        .\%6 := \:(\%1[\%9:1])                 # Current digit
        .\%7 := \:(\%2[\%9:1])                 # of each
        increment \%6 \%7+\%c                  # Form sum + carry
        .\%5 ::= \%6 % 10                      # Separate sum+carry 
        .\%c ::= \%6 / 10                      # into digits.
        .\%s := \%5\%s                         # Accumulate sum
    }
    if \%c .\%s := \%c\%s                      # Final carry (if any)
    return \%s                                 # Return result
}

# Macro DECIMALTIMES
# Multiplies two unsigned decimal strings regardless of magnitude by
# repetitive addition.  Practical only when one of the factors is small and
# the other one is (or the result would be) bigger than the hardware integer
# size.  \%1, \%2 are the factors.  Returns product as decimal string.
#
# Order of args doesn't matter.  The smaller one is automatically chosen
# as the loop counter.  Note the comparison of argument lengths rather than
# values, since the > operator won't work with numbers that are too big for
# the word size, nor can big numbers be used as loop variables.
#
def DECIMALTIMES {
    local \%s \%c
    if > \flen(\%1) \flen(\%2) { .\%9 := \%1, .\%1 := \%2, .\%2 := \%9 }
    .\%s = 0
    for \%9 1 \%1 1 {                         # Add X to itself Y times
        .\%s := \fexec(decimaladd \%2 \%s)
    }
    return \%s
}

# Macro HEXTODEC
# Converts a two's complement hexadecimal string into a signed decimal string.
# \%1 = hexadecimal argument.
# Returns signed decimal string.
#
define HEXTODEC {
    local digits \%b \%d \%p
    .digits := \flen(\%1)
    if not \m(digits) end 1 "\%0: NO ARGUMENT GIVEN"
    .\%1 := \fupper(\%1)
    if \fverify(0123456789ABCDEF,\%1) end 1 "\%0: '\%1' NOT A HEX STRING"
    if not \findex(\:(\%1[1:1]),89ABCDEF) {  # Positive number
        .\%d = 0
        .\%p = 0
        for \%9 \flen(\%1) 1 -1 {  # Loop through digits right to left
            .\%6 := \:(\%1[\%9:1])                    # Hex digit
            .\%6 := \fradix(\%6,16,10)                # Decimal value
            .\%4 := \fexec(powerof16 \%p)             # Current power of 16
            .\%6 := \fexec(decimaltimes \%4 \%6)      # Times power of 16
            .\%d := \fexec(decimaladd \%6 \%d)        # Add to result
            increment \%p                             # Next power of 16
        }
        return \%d
    }
    # Negative number (bit 0 set)
    if = 1 \findex(\%1,800000000000000000000000000) { # Special case
        .\%b ::= \flen(\%1) * 4         # Look this one up in our table
        .\%b := \m(maxplusone<\%b>)     # to avoid infinite recursion
        if not def \%b .\%b = ERROR
        return -\%b
    }
    .\%b := \fexec(hextobin \%1)        # Normal case - convert to binary
    .\%7 := \flen(\%b)                  # Get length of binary
    .\%b := \fexec(twoscomplement \%b)  # Get two's complement
    .\%b := \fexec(bintohex \%b \%7)    # Convert to hex
    .\%d := \fexec(hextodec \%b)        # Call ourselves to convert to decimal
    return -\%d
}

# Test HEXTODEC...

.t0 := \v(ftime)                        # Start time for test suite

echo ****************
echo TESTING HEXTODEC...
echo ****************
def try {
    local result
    .t1 := \v(ftime)                    # Current time
    .result := \fexec(hextodec \%1)
    .t2 := \v(ftime)                    # New time
    (setq t3 (- t2 t1))                 # Difference
    echo HEX \%1 = DEC \m(result) [\ffpround(\m(t3),2) sec] # Print
}


try 0
try 7
try 8
try F
try 1234
try 80
try 83
try xxx
try ffff
try 8000
try 8001
try 5555
try 12345
try fffffffffffffffe
try 0000000000000000
try 00002ee000000000
try 0000123456789abc
try 00002ee000012345
try 2ee0000000000000
try aee0000000000000
try f0000000fffffffe
try 20000000fffffffe
try 7fffffffffffffffffffffffffffffff

# TEST DECTOHEX...

echo ****************
echo TESTING DECTOHEX...
echo ****************
def try {
    local result
    # Note \v(time) lacks the fractional part in Windows for some reason.
    .t1 := \v(ftime)                    # Current time
    .result := \fexec(dectohex \%1 \%2) # Do the conversion
    .t2 := \v(ftime)                    # New time
    (setq t3 (- t2 t1))                 # Difference
    echo \%1[\%2] = \m(result) [\ffpround(\m(t3),2) sec] # Print
}
try 7          # No word size specified

try  7 4       # 4-bit word
try  8 4
try -8 4
try -9 4
try 99 4

try  0 8        # 8-bit word
try -0 8
try  1 8
try +1 8
try  2 8
try  3 8
try  4 8
try  5 8
try  6 8
try  7 8
try -1 8
try -2 8
try -3 8
try -4 8
try -5 8
try -6 8
try -7 8
try -8 8
try 64 8
try 65 8
try -128 8

try 0 16       # 16-bit word
try 64 16
try 65 16
try -128 16
try -32768 16
try 99999 16
try -99999 16

try 0 32       # 32-bit word
try 1 32
try 16383 32
try 2147483647 32
try -1 32
try -2 32
try -2147483647 32
try -2147483648 32

try 0 64       # 64-bit word
try 2147483647 64
try -1 64
try -2 64
try  1234567890 64
try -2147483647 64
try -2147483648 64
try  8224373093854475231 64

try 0 128      # 128-bit word
try 1 128
try -1 128
try -2 128
try 317282366902934863643347307341786875499 128

.t3 := \v(ftime)                        # End time for test suite
(setq t3 (- t3 t0))
echo TOTAL TIME: \ffpround(\m(t3),2) sec

# Don't exit in K95 or else the window will disappear and the results too.

if c-kermit exit
