Asmusr Posted May 11, 2017 Share Posted May 11, 2017 My little article on differential calculations was very well received, so here's one about another favorite of mine: fixed point numbers. In assembly our data are stored as either bytes (8-bit) or words (16-bit). For storing numbers we usually consider these bits as representing pure binary numbers, but there are alternatives like BCD, which are beyond the scope of this article. We can use a word to hold an unsigned integer between 0 and 65535, or, if we need both positive and negative numbers, we can choose to consider a word a 2's complement number in the range -32768 to 32767. Unsigned: ------------------------ 0: 0000000000000000 1: 0000000000000001 32768: 1000000000000000 65535: 1111111111111111 | Signed 2's complement: ------------------------ -32768: 1000000000000000 -1: 1111111111111111 0: 0000000000000000 1: 0000000000000001 32767: 0111111111111111 How do we represent numbers that are not integers but have a fractional part? For instance if we have sprites that should move less than one pixel per frame. In BASIC we have floating point numbers that can hold a wide range of values, but those are expensive in both speed and storage. In assembly - and especially for games development - we want something smaller and faster. What we can do is to decide that binary numbers represent fractions of real numbers rather than integers. So instead of deciding that 000000110 represents the integer 6 we could choose that it represents 6/100. The number 10000110 would then represent (128+6)/100 = 134/100 = 1.34. This works, but dividing by 100 to find the integer part is costly compared to other operations in assembly, so we usually choose a scale of 128 or another multiple of 2 that we can divide or multiply by using binary shifting alone. If our scale is 128 and we consider a 16-bit word, 9 bits are used to represent the integer part and 7 bits are used to represent the fraction. 1: 000000001.0000000 1.34: 000000001.0000110 0.5: 000000000.1000000 2.25: 000000010.0100000 127: 111111111.0000000 We can call this representation 9.7 fixed point. It depends on the task how many bits we need to allocate - or can allocate - to the fractional part. 8.8 fixed point numbers are particularly easy to work with since the integer part is simply the most significant byte. This is very useful for sprite positions where we can just send the MSB to the VDP, but if the required range of the integer part is beyond -128 - 127 (signed) or 0 - 255 (unsigned) we need to allocate fewer bits to the fraction and more bits to the integer part. It's easy to do calculations on fixed point numbers if we obey a few simple rules: - Addition and subtraction can only be done on numbers with the same number of fractional bits. If they don't have the same number of fractional bits, one of them has to be shifted first. We can use the usual addition and subtraction assembly instructions - also for signed numbers. - Multiplication can be done on fixed point numbers with any number of fractional bits. If the first number has 8 fractional bits and the second number has 6 fractional bits we end up with a result with 8+6=14 fractional bits, so we need to shift this 6 places right to end up with 8 fractional bits again. - Division works the opposite way, so if we divide a number with f1 fractional bits by a number with f2 fractional bits we get f1-f2 fractional bits. To end up with f1 fractional bits we can shift the first number left f2 positions *before* performing the division (if we do it after we will lose precision). With multiplication and division we have to remember that the assembly instructions and unsigned, so the sign might have to be cleared before and reassigned after the instruction. However, if we multiply small numbers where the result doesn't exceed 16 bits, we can actually use the mpy instruction as it is on signed numbers (trust me!). 7 Quote Link to comment Share on other sites More sharing options...
+TheBF Posted May 11, 2017 Share Posted May 11, 2017 Very cool. This has direct application in C and Forth as well. C and Forth programs have traditionally made heavy use of integers vs floating point for efficiency too. Thanks for these academic insights into things. Quote Link to comment Share on other sites More sharing options...
sometimes99er Posted May 12, 2017 Share Posted May 12, 2017 Very nice. Thanks. Quote Link to comment Share on other sites More sharing options...
RXB Posted May 12, 2017 Share Posted May 12, 2017 Extended Basic uses all of them. I even posted he XB Source code in GPL and ROMs that show how XB does this. Some of the code is overly complicated to keep with TI being a Calculator Company. Quote Link to comment Share on other sites More sharing options...
Willsy Posted May 12, 2017 Share Posted May 12, 2017 I'd really like a fixed point library for TurboForth. That would be awesome. Quote Link to comment Share on other sites More sharing options...
Asmusr Posted May 12, 2017 Author Share Posted May 12, 2017 I'd really like a fixed point library for TurboForth. That would be awesome. If you create a fixed point library, one of the first decisions is how much information you want to store about each FP number. Do you store just the binary number and leave it to the user of the library to specify how many places to shift the result after a multiplication, for instance? Or do you store the number of fractional bits for each FP number and use this to shift automatically? You can also store whether a FP number is signed or not. If it's unsigned you can speed up multiplications and divisions. If you store the number of fractional bits you can report an error if you try to add or subtract numbers with different number of fractional bits, or you can scale the numbers automatically. You also need to decide how to handle overflows, do you just ignore them, or report an error, or return the maximum possible result? Quote Link to comment Share on other sites More sharing options...
Asmusr Posted May 12, 2017 Author Share Posted May 12, 2017 Extended Basic uses all of them. I even posted he XB Source code in GPL and ROMs that show how XB does this. Some of the code is overly complicated to keep with TI being a Calculator Company. Do you mean it's using floating point? This is fixed point. Quote Link to comment Share on other sites More sharing options...
+TheBF Posted May 12, 2017 Share Posted May 12, 2017 If you create a fixed point library, one of the first decisions is how much information you want to store about each FP number. Do you store just the binary number and leave it to the user of the library to specify how many places to shift the result after a multiplication, for instance? Or do you store the number of fractional bits for each FP number and use this to shift automatically? You can also store whether a FP number is signed or not. If it's unsigned you can speed up multiplications and divisions. If you store the number of fractional bits you can report an error if you try to add or subtract numbers with different number of fractional bits, or you can scale the numbers automatically. You also need to decide how to handle overflows, do you just ignore them, or report an error, or return the maximum possible result? Many of the old Forth systems resorted to a 32 bit library for fixed point math to prevent overflow. I have never thought about creating a 16 bit version. I would be useful for scientific applications if you were data logging low voltages and currents I suppose. Interesting... The creator of Forth made a couple of operators to help with 16bit overflow in calculations. One is '*/' called "star-slash". Arguments are ( n, multiplier, divisor ) and it returns 16bit int. You use it to scale values that could overflow on the multiply operation because the mpy is mixed math producing a 32 bit product The other handy one is called M+ which takes 2 ints and returns a 32bit int. B Quote Link to comment Share on other sites More sharing options...
+TheBF Posted May 12, 2017 Share Posted May 12, 2017 (edited) Hey Mark, I think you already have a fixed point library! 299.99 fixed point is still just 29999 internally. What Forth does is provides a set of words to format any number as fixed point numbers. First you need this little word set. Believe it or not this allows arbitrary number formatting in 114 bytes of code on a 16 bit machine. ( All these routines assume a 32 bit number on the stack (ie: 2 16 bit ints) which makes them much more practical for money programs. From CAMEL99 source code : UD/MOD ( ud1 u2 -- u3 ud4) >R 0 R@ UM/MOD -ROT R> UM/MOD ROT ; \ 32/16->32 divide : HOLD ( char -- ) -1 HP +! HP @ C! ; \ decr. HOLD pointer HP, Store char at the address contained in HP \ : >DIGIT ( n -- c) DUP 9 > 7 AND + 30 + ; \ convert n to ascii digit c (*Moved to ASM word because it is in a loop) : <# ( --) #PAD HP ! ; \ initialize Hold Pointer to end of the number buffer (#pad) : # ( ud1 -- ud2) BASE @ UD/MOD ROT >DIGIT HOLD ; \ convert 1 digit & store at HP, return remainder : #S ( ud1 -- ud2) BEGIN # 2DUP OR 0= UNTIL ; \ convert all digits in ud1. ud2 will be 0 (the remainder) : #> ( ud1 -- c-addr u) 2DROP HP @ #PAD OVER - ; \ return a stack string (address, length) of the converted number : SIGN ( n -- ) 0< IF [CHAR] - HOLD THEN ; \ if 'n'<0 add '-' char string created in #PAD Then you use these routines to make your number formats. The simplest is below; : U. ( u -- ) S>D <# #S #> TYPE SPACE ; \ print 'u' as an un-signed integer But here is signed dollar formatting \ From CAMEL Forth source code Brad Rodriguez : DNEGATE ( d -- d) SWAP INVERT SWAP INVERT 1 M+ ; : ?DNEGATE ( d1 n -- d2) 0< IF DNEGATE THEN ; \ negate d1 if n negative : DABS ( d1 -- +d2 ) DUP ?DNEGATE ; \ absolute value dbl.prec. CHAR . CONSTANT '.' \ from STARTING Forth, Brodie : .$ ( n -- ) S>D TUCK DABS <# # # '.' HOLD #S ROT SIGN [CHAR] $ HOLD #> TYPE SPACE ; Works like this: 29950 .$ $299.50 -30095 .$ $-300.95 Edited May 12, 2017 by TheBF Quote Link to comment Share on other sites More sharing options...
Willsy Posted May 12, 2017 Share Posted May 12, 2017 Brian I already have a 32 bit library. It has a ton of words in it including hold and <# etc. Maybe I could extend it to provide fixed point? Quote Link to comment Share on other sites More sharing options...
RXB Posted May 12, 2017 Share Posted May 12, 2017 Do you mean it's using floating point? This is fixed point. It uses all of them depending on the routines but only returns Floating Point and Decimal. The ROM even has a Binary converter it uses sometimes but never outputs any of these features. Seemed odd that TI would restrict this so much on the TI99/4A? Quote Link to comment Share on other sites More sharing options...
+TheBF Posted May 12, 2017 Share Posted May 12, 2017 Brian I already have a 32 bit library. It has a ton of words in it including hold and <# etc. Maybe I could extend it to provide fixed point? I think it should be pretty straightforward with all that. It really is just creating the output operators for the fixed size you want to use isn't it? Or am I missing something? All the maths will work out of the box. I suppose you could "tart" things up with a special vocabulary or even an infix parser. Depends what you want I guess. B Quote Link to comment Share on other sites More sharing options...
Willsy Posted May 12, 2017 Share Posted May 12, 2017 Yeah I guess so. If I had a word to define how many decimal places one requires and base it all on 32 bit integers it should be fairly straightforward. I mean, if I want 2 decimals then everything is internally multiplied by 100 right? I'd keep it simple so you couldn't have mixed decimal lengths. You decide up front how many decimal places you want to work with. Quote Link to comment Share on other sites More sharing options...
+TheBF Posted May 12, 2017 Share Posted May 12, 2017 Had to step away. Yes I believe that's it in a nut shell. And with 32bit math you can build a financial package that 's good to 21 474 836 pounds sterling and 47 P or so. :-) Quote Link to comment Share on other sites More sharing options...
+mizapf Posted May 12, 2017 Share Posted May 12, 2017 These are the fixed point routines that I actually used in my FRACTALS program, which makes use of the on-chip RAM of the TMS9995 in the Geneve. Sorry for the sparse comments; I can try to add them if anyone is interested. * Fixed point routines * * Format: LI R0,VALUE1 * LI R1,VALUE2 * LI R2,RESULT * BLWP @FXMUL * * => VALUE1*VALUE2=RESULT * * LI R0,VALUE1 * LI R1,VALUE2 * BLWP @FXADD * * => VALUE1+VALUE2=VALUE1 * * * Fixed point format: 8 bytes * 2 bytes integer * 6 bytes fraction * * xxxx.yyyy yyyy yyyy * MATWS EQU >F020 SIGN EQU >F048 INCR EQU >F080 FMOVE EQU >F072 FXADD EQU >F044 FXMUL EQU >F040 FMULOC EQU >F090 * ====================on-chip======================= ONCHIP DATA MATWS,FMUL FXMUL DATA MATWS,>F04A FXADD DATA 0 MOV *R13,R3 F04A MOV R13,R12 MOV @2(R13),R4 LI R8,3 LI R6,6 A R6,R4 A R6,R3 FADD1 A *R4,*R3 JNC FADD2 MOV R3,R7 BL @INCR FADD2 DECT R4 DECT R3 DEC R8 JOC FADD1 FADD3 RTWP FMOVEL MOV *R11+,R0 FMOVE MOV *R11+,R1 MOV *R0+,*R1+ MOV *R0+,*R1+ MOV *R0+,*R1+ MOV *R0,*R1 RT MOV R7,R5 INCR INCR1 DECT R5 C R5,*R12 JL INCR2 INC *R5 MOV *R5,*R5 JEQ INCR1 INCR2 RT FMUL3 DECT R4 FMULOC A R10,R7 A R6,R3 CLR R8 FMUL4 MOV *R4,R0 JNE FMUL4A CLR R8 DECT R7 DECT R4 C R4,R9 JHE FMUL4 JMP FMUL6A FMUL4A MOV *R3,R1 JEQ FMUL4B MPY R0,R1 A R8,R2 JNC $+4 INC R1 FMUL4B A R2,*R7 JNC $+6 BL @INCR FMUL5 MOV R1,R8 MOV R1,R2 DECT R3 DECT R7 C R3,*R13 JHE FMUL4A C R7,*R12 JL FMUL6 A R8,*R7 so we don't lose carry FMUL6 C R4,R9 JH FMUL3 FMUL6A B @FMULCN * ============================================== ** Change sign CHSIGN MOV R0,R1 AI R1,8 CHSGN1 DECT R1 C R1,R0 JL CHSGNE MOV *R1,R2 JEQ CHSGN1 NEG *R1 CHSGN2 DECT R1 C R1,R0 JL CHSGNE INV *R1 JMP CHSGN2 CHSGNE RT ** Multiplication routine FMUL MOV R13,R12 MOV *R12+,R3 MOV *R12+,R4 MOV R4,R9 MOV *R12,R7 CLR @SIGN MOV *R3,R1 JEQ FMUL1 JGT FMUL1 INV @SIGN MOV R3,R0 BL @CHSIGN C R3,R4 JNE FMUL1 NEG @SIGN same factors JMP FMUL2 don't change sign FMUL1 MOV *R4,R1 JEQ FMUL2 JGT FMUL2 INV @SIGN MOV R4,R0 BL @CHSIGN FMUL2 MOV R7,R8 LI R6,7 CLR *R8+ DEC R6 JNE $-4 LI R6,8 LI R10,6 A R10,R7 A R6,R4 CLR R2 DECT R3 B @FMULOC use on-chip routine FMULCN AI R7,10 MOV *R7,R0 JEQ FMUL8 JGT FMUL8 FMUL7 BL @INCR FMUL8 MOV @SIGN,R0 JEQ FMULE JGT FMULE MOV *R12,R0 BL @CHSIGN FMULE RTWP ... LI R0,ONCHIP Copy the math routines LI R1,>F040 to the on-chip RAM OCC MOV *R0+,*R1+ CI R1,>F0D6 JNE OCC Quote Link to comment Share on other sites More sharing options...
+TheBF Posted May 13, 2017 Share Posted May 13, 2017 Cool so these are 64 bit math operations. I just may re-code these in Forth Assembler and give them a try. Thanks! Quote Link to comment Share on other sites More sharing options...
Recommended Posts
Join the conversation
You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.