# 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