home *** CD-ROM | disk | FTP | other *** search
/ Columbia Kermit / kermit.zip / ckscripts / twoscomplementv3 < prev    next >
Text File  |  2020-01-01  |  14KB  |  411 lines
  1. # TWOSCOMPLEMENT with Large Numbers...
  2. #
  3. # Kermit macros to convert signed decimal numbers to two's complement
  4. # hexadecimal notation and vice versa:
  5. #
  6. # DECTOHEX d n
  7. #   Converts the decimal argument d to n-bit two's complement hex format;
  8. #   n should be 4, 8, 16, 32, 64, or 128.
  9. #   Example: "DECTOHEX -1 32" returns "FFFFFFFF".
  10. #
  11. # HEXTODEC h
  12. #   Converts the hexadececimal two's-complement argument to signed decimal. 
  13. #   Example: "HEXTODEC FFFFFFFF" returns "-1".
  14. #
  15. # This version does the big calculations with strings, rather than machine
  16. # integers, so is able (in principle) to handle integers of any size.  As
  17. # written it accommodates word sizes of 4, 8, 16, 32, 64, and 128.  The main
  18. # application is on 32-bit hardware or Kermit versions (notably K95) built
  19. # with 32-bit memory models when it is necessary to do decimal/hexadecimal
  20. # conversions of larger numbers.  Since this version uses strings and not
  21. # built-in machine arithmetic, it is considerably slower than the
  22. # straightforward version would be, but still tolerable on modern hardware.
  23. #
  24. # Requires C-Kermit 8.0 or later or Kermit 95 2.0 or later.
  25. #
  26. # Search terms:
  27. #   BIGNUM decimal/hexadecimal format conversion macro implementation;
  28. #   string arithmetic; manipulation of large numbers as strings.
  29. #   Decimal/binary conversion of big numbers.
  30. # 
  31. # F. da Cruz, Columbia University, Dec 2007 - Jan 2008
  32. # Last update: Wed Jan  9 12:21:06 2008
  33.  
  34. # Largest positive integer for the supported word sizes
  35.  
  36. .maxint<4> = 7
  37. .maxint<8> = 127
  38. .maxint<16> = 32767
  39. .maxint<32> = 2147483647
  40. .maxint<64> = 9223372036854775807
  41. .maxint<128> = 340282366920938463463374607431768211455
  42.  
  43. # Ditto plus one (because we can't necessarily do arithmetic on big numbers)
  44.  
  45. .maxplusone<4> = 8
  46. .maxplusone<8> = 128
  47. .maxplusone<16> = 32768
  48. .maxplusone<32> = 2147483648
  49. .maxplusone<64> = 9223372036854775808
  50. .maxplusone<128> = 340282366920938463463374607431768211456
  51.  
  52. # Powers of 16 up to 32 (128 bits)
  53.  
  54. def POWEROF16 {  # This is a macro to keep the array private.
  55.     local &p
  56.     dcl \&p[] = 16 -
  57.      256 -
  58.      4096 -
  59.      65536 -
  60.      1048576 -
  61.      16777216 -
  62.      268435456 -
  63.      4294967296 -
  64.      68719476736 -
  65.      1099511627776 -
  66.      17592186044416 -
  67.      281474976710656 -
  68.      4503599627370496 -
  69.      72057594037927936 -
  70.      1152921504606846976 -
  71.      18446744073709551616 -
  72.      295147905179352825856 -
  73.      4722366482869645213696 -
  74.      75557863725914323419136 -
  75.      1208925819614629174706176 -
  76.      19342813113834066795298816 -
  77.      309485009821345068724781056 -
  78.      4951760157141521099596496896 -
  79.      79228162514264337593543950336 -
  80.      1267650600228229401496703205376 -
  81.      20282409603651670423947251286016 -
  82.      324518553658426726783156020576256 -
  83.      5192296858534827628530496329220096 -
  84.      83076749736557242056487941267521536 -
  85.      1329227995784915872903807060280344576 -
  86.      21267647932558653966460912964485513216 -
  87.      340282366920938463463374607431768211456
  88.     .\&p[0] = 1 # Because initialers start at 1.
  89.     if not integer \%1 end 1 "\%0: NON-NUMERIC ARGUMENT '%1'"
  90.     if ( < \%1 0 || > \%1  32 ) \%1 end 1 "\%0: ARGUMENT OUT OF RANGE '\%1'"
  91.     return \&p[\%1]
  92. }
  93.  
  94. # Macro BINTOHEX converts a binary string to hex.
  95. #   \%1 = binary string to be converted
  96. #   \%2 = word size in bits
  97. #   Returns hex string
  98. #
  99. define BINTOHEX {
  100.     undef \%6                                # Result accumulator
  101.     .\%1 := \flpad(\%1,\%2,0)                # Pad to size if necessary
  102.     for \%9 1 \%2 4 {                        # Do four bits at at a time
  103.         .\%8 := \fsubstr(\%1,\%9,4)          # Get chunk of 4
  104.         if not def \%8 break                 # Make sure we have one
  105.         .\%7 := \fradix(\%8,2,16)            # Convert to Hex digit
  106.         .\%6 := \%6\%7                       # Accumulate
  107.     }
  108.     return \%6
  109. }
  110.  
  111. # HEXTOBIN converts hex string to binary
  112. define HEXTOBIN {
  113.     undef \%7
  114.     for \%9 1 \flen(\%1) 1 {
  115.         .\%7 := \%7\flpad(\fradix(\:(\%1[\%9:1]),16,2),4,0)
  116.     }
  117.     return \%7
  118. }
  119.  
  120. # Macro DTOB converts a decimal string to binary.
  121. #  \%1 = decimal string to be converted
  122. #  Returns binary string
  123. #
  124. def DTOB {                                   # Convert decimal string to binary
  125.     local div2 result remainder
  126.     def DIV2 {                               # Divide decimal string by two
  127.         local \%i
  128.         undef \%6 \%7 result
  129.         for \%i 1 \flen(\%1) 1 {             # One digit at a time.
  130.             .\%9 := \%7\:(\%1[\%i:1])        # Get a digit.
  131.             .\%8 ::= \%9/2                   # Divide it by 2
  132.             .\%7 ::= \%9%2                   # Get remainder
  133.             .\%6 := \%6\%8                   # Accumulate result
  134.         }
  135.         .result := \%6                       # These are just
  136.         .remainder := \%7                    # for clarity...
  137.     }
  138.     while true {                             # Convert by repetitive division.
  139.         div2 \%1                             # Divide decimal number by 2
  140.         .\%6 := \m(remainder)\%6             # Accumulate result...
  141.         .\%1 := \m(result)
  142.         if not \fverify(0,\%1) break         # Quit when there's nothing left.
  143.     }
  144.     return \%6
  145. }
  146.  
  147. # Macro TWOSCOMPLEMENT converts binary string into its two's complement
  148. #  \%1 = binary string
  149. #  \%2 = number of bits (if not given, length of \%1 is used)
  150. #  Returns the 2's complement of the given binary string
  151. #
  152. define TWOSCOMPLEMENT {
  153.     if not def \%2 .\%2 = \flen(\%1)         # Supply length if not given
  154.     .\%9 := \flpad(\%1,\%2,0) }              # Left-pad to desired length
  155.     .\%8 ::= \frindex(1,\%9) - 1             # Find first 1 from the right
  156.     if == \%8 -1 return \frepeat(0,\%2 / 4)  # Watch out for negative 0
  157.     .\%7 := \fsubstr(\%9,1,\%8)              # Split string here
  158.     .\%6 := \fsubstitute(\%7,01,10)          # Complement bits in left part
  159.     .\%5 := \%6\fsubstr(\%9,\%8+1)           # Put back with right part
  160.     return \%5
  161. }
  162.  
  163. # Macro DECTOHEX converts a signed decimal number to 2's complement hexadecimal
  164. # using the macros defined above as workers.
  165. #   \%1 = decimal number string (default 0)
  166. #   \%2 = word size in bits
  167. #         (must be a power of two, 4 or greater, default 32, max 128)
  168. #   Returns the hex result of the requested size.
  169. #
  170. define DECTOHEX {
  171.     local digits legal
  172.     .legal = :4:8:16:32:64:128:              # Legal word sizes for dec-to-hex
  173.     if not def \%1 .\%1 = 0                  # Supply default if no arg given
  174.     if not numeric \%1 return NOT_A_NUMBER:\%1  # Check that arg is a number
  175.     if not def \%2 .\%2 := 32                   # Use 32 bits if no second arg
  176.     if not \findex(:\%2:,\m(legal)) end 1 "UNSUPPORTED WORD SIZE - \%2"
  177.     .digits := \flen(\m(maxint<\%2>))           # Number of digits in it
  178.  
  179.     if eq "\fsubstr(\%1,1,1)" "+" .\%1 := \fsubstr(\%1,2) # strip any + sign
  180.     if not eq "\fsubstr(\%1,1,1)" "-" {      # If argument is not signed...
  181.         if lgt \flpad(\%1,\m(digits),0) \m(maxint<\%2>) return OVERFLOW
  182.         dtob \%1                             # Convert from decimal to binary
  183.         bintohex \v(return) \%2              # And from binary to hex
  184.         return \flpad(\v(return),(\%2/4),0)  # Return padded result
  185.     }
  186.     .\%1 := \fsubstr(\%1,2)                  # Negative number - remove sign
  187.     .\%1 := \flpad(\%1,\flen(\m(maxint<\%2>)),0) # Must use lexical comparison
  188.     if llt \m(maxplusone<\%2>) \%1 return UNDERFLOW # Check magnitude
  189.     dtob \%1                                 # Convert to binary
  190.     .\%5 := \fexec(twoscomplement \v(return) \%2) # Get two's complement
  191.     .\%4 := \fexec(bintohex \%5 \%2)         # Convert to hex
  192.     return \%4
  193. }
  194.  
  195. # IS32BIT checks if positive number fits in 32 bits.
  196. # Could be used for optimization but not worth it.
  197. #
  198. def IS32BIT {
  199.     .\%1 := \flpad(\ftrim(\%1,0),10,0)
  200.     if lgt \%1 2147483647 return 0
  201.     return 1
  202. }
  203.  
  204. # Macro DECIMALADD adds two unsigned decimal strings regardless of magnitude.
  205. # \%1, \%2 are decimal strings.
  206. # Returns sum as decimal string.
  207. #
  208. def DECIMALADD {
  209.     local \%s \%c
  210.     .\%9 := \fmax(\flen(\%1),\flen(\%2))       # Get length of longest arg
  211.     .\%1 := \flpad(\%1,\%9,0)                  # Pad both to same length
  212.     .\%2 := \flpad(\%2,\%9,0)
  213.     .\%c = 0                                   # Carry
  214.     undef \%s                                  # Sum accumulator
  215.     for \%9 \flen(\%1) 1 -1 {                  # Loop through digits RTL
  216.         .\%6 := \:(\%1[\%9:1])                 # Current digit
  217.         .\%7 := \:(\%2[\%9:1])                 # of each
  218.         increment \%6 \%7+\%c                  # Form sum + carry
  219.         .\%5 ::= \%6 % 10                      # Separate sum+carry 
  220.         .\%c ::= \%6 / 10                      # into digits.
  221.         .\%s := \%5\%s                         # Accumulate sum
  222.     }
  223.     if \%c .\%s := \%c\%s                      # Final carry (if any)
  224.     return \%s                                 # Return result
  225. }
  226.  
  227. # Macro DECIMALTIMES
  228. # Multiplies two unsigned decimal strings regardless of magnitude by
  229. # repetitive addition.  Practical only when one of the factors is small and
  230. # the other one is (or the result would be) bigger than the hardware integer
  231. # size.  \%1, \%2 are the factors.  Returns product as decimal string.
  232. #
  233. # Order of args doesn't matter.  The smaller one is automatically chosen
  234. # as the loop counter.  Note the comparison of argument lengths rather than
  235. # values, since the > operator won't work with numbers that are too big for
  236. # the word size, nor can big numbers be used as loop variables.
  237. #
  238. def DECIMALTIMES {
  239.     local \%s \%c
  240.     if > \flen(\%1) \flen(\%2) { .\%9 := \%1, .\%1 := \%2, .\%2 := \%9 }
  241.     .\%s = 0
  242.     for \%9 1 \%1 1 {                         # Add X to itself Y times
  243.         .\%s := \fexec(decimaladd \%2 \%s)
  244.     }
  245.     return \%s
  246. }
  247.  
  248. # Macro HEXTODEC
  249. # Converts a two's complement hexadecimal string into a signed decimal string.
  250. # \%1 = hexadecimal argument.
  251. # Returns signed decimal string.
  252. #
  253. define HEXTODEC {
  254.     local digits \%b \%d \%p
  255.     .digits := \flen(\%1)
  256.     if not \m(digits) end 1 "\%0: NO ARGUMENT GIVEN"
  257.     .\%1 := \fupper(\%1)
  258.     if \fverify(0123456789ABCDEF,\%1) end 1 "\%0: '\%1' NOT A HEX STRING"
  259.     if not \findex(\:(\%1[1:1]),89ABCDEF) {  # Positive number
  260.         .\%d = 0
  261.         .\%p = 0
  262.         for \%9 \flen(\%1) 1 -1 {  # Loop through digits right to left
  263.             .\%6 := \:(\%1[\%9:1])                    # Hex digit
  264.             .\%6 := \fradix(\%6,16,10)                # Decimal value
  265.             .\%4 := \fexec(powerof16 \%p)             # Current power of 16
  266.             .\%6 := \fexec(decimaltimes \%4 \%6)      # Times power of 16
  267.             .\%d := \fexec(decimaladd \%6 \%d)        # Add to result
  268.             increment \%p                             # Next power of 16
  269.         }
  270.         return \%d
  271.     }
  272.     # Negative number (bit 0 set)
  273.     if = 1 \findex(\%1,800000000000000000000000000) { # Special case
  274.         .\%b ::= \flen(\%1) * 4         # Look this one up in our table
  275.         .\%b := \m(maxplusone<\%b>)     # to avoid infinite recursion
  276.         if not def \%b .\%b = ERROR
  277.         return -\%b
  278.     }
  279.     .\%b := \fexec(hextobin \%1)        # Normal case - convert to binary
  280.     .\%7 := \flen(\%b)                  # Get length of binary
  281.     .\%b := \fexec(twoscomplement \%b)  # Get two's complement
  282.     .\%b := \fexec(bintohex \%b \%7)    # Convert to hex
  283.     .\%d := \fexec(hextodec \%b)        # Call ourselves to convert to decimal
  284.     return -\%d
  285. }
  286.  
  287. # Test HEXTODEC...
  288.  
  289. .t0 := \v(ftime)                        # Start time for test suite
  290.  
  291. echo ****************
  292. echo TESTING HEXTODEC...
  293. echo ****************
  294. def try {
  295.     local result
  296.     .t1 := \v(ftime)                    # Current time
  297.     .result := \fexec(hextodec \%1)
  298.     .t2 := \v(ftime)                    # New time
  299.     (setq t3 (- t2 t1))                 # Difference
  300.     echo HEX \%1 = DEC \m(result) [\ffpround(\m(t3),2) sec] # Print
  301. }
  302.  
  303.  
  304. try 0
  305. try 7
  306. try 8
  307. try F
  308. try 1234
  309. try 80
  310. try 83
  311. try xxx
  312. try ffff
  313. try 8000
  314. try 8001
  315. try 5555
  316. try 12345
  317. try fffffffffffffffe
  318. try 0000000000000000
  319. try 00002ee000000000
  320. try 0000123456789abc
  321. try 00002ee000012345
  322. try 2ee0000000000000
  323. try aee0000000000000
  324. try f0000000fffffffe
  325. try 20000000fffffffe
  326. try 7fffffffffffffffffffffffffffffff
  327.  
  328. # TEST DECTOHEX...
  329.  
  330. echo ****************
  331. echo TESTING DECTOHEX...
  332. echo ****************
  333. def try {
  334.     local result
  335.     # Note \v(time) lacks the fractional part in Windows for some reason.
  336.     .t1 := \v(ftime)                    # Current time
  337.     .result := \fexec(dectohex \%1 \%2) # Do the conversion
  338.     .t2 := \v(ftime)                    # New time
  339.     (setq t3 (- t2 t1))                 # Difference
  340.     echo \%1[\%2] = \m(result) [\ffpround(\m(t3),2) sec] # Print
  341. }
  342. try 7          # No word size specified
  343.  
  344. try  7 4       # 4-bit word
  345. try  8 4
  346. try -8 4
  347. try -9 4
  348. try 99 4
  349.  
  350. try  0 8        # 8-bit word
  351. try -0 8
  352. try  1 8
  353. try +1 8
  354. try  2 8
  355. try  3 8
  356. try  4 8
  357. try  5 8
  358. try  6 8
  359. try  7 8
  360. try -1 8
  361. try -2 8
  362. try -3 8
  363. try -4 8
  364. try -5 8
  365. try -6 8
  366. try -7 8
  367. try -8 8
  368. try 64 8
  369. try 65 8
  370. try -128 8
  371.  
  372. try 0 16       # 16-bit word
  373. try 64 16
  374. try 65 16
  375. try -128 16
  376. try -32768 16
  377. try 99999 16
  378. try -99999 16
  379.  
  380. try 0 32       # 32-bit word
  381. try 1 32
  382. try 16383 32
  383. try 2147483647 32
  384. try -1 32
  385. try -2 32
  386. try -2147483647 32
  387. try -2147483648 32
  388.  
  389. try 0 64       # 64-bit word
  390. try 2147483647 64
  391. try -1 64
  392. try -2 64
  393. try  1234567890 64
  394. try -2147483647 64
  395. try -2147483648 64
  396. try  8224373093854475231 64
  397.  
  398. try 0 128      # 128-bit word
  399. try 1 128
  400. try -1 128
  401. try -2 128
  402. try 317282366902934863643347307341786875499 128
  403.  
  404. .t3 := \v(ftime)                        # End time for test suite
  405. (setq t3 (- t3 t0))
  406. echo TOTAL TIME: \ffpround(\m(t3),2) sec
  407.  
  408. # Don't exit in K95 or else the window will disappear and the results too.
  409.  
  410. if c-kermit exit
  411.