Home » Archimedes archive » Archimedes World » AW-1996-03-Disc 2.adf » !AcornAns_AcornAns » September/FastDiv/ReadMe
September/FastDiv/ReadMe
This website contains an archive of files for the Acorn Electron, BBC Micro, Acorn Archimedes, Commodore 16 and Commodore 64 computers, which Dominic Ford has rescued from his private collection of floppy disks and cassettes.
Some of these files were originally commercial releases in the 1980s and 1990s, but they are now widely available online. I assume that copyright over them is no longer being asserted. If you own the copyright and would like files to be removed, please contact me.
| Tape/disk: | Home » Archimedes archive » Archimedes World » AW-1996-03-Disc 2.adf » !AcornAns_AcornAns |
| Filename: | September/FastDiv/ReadMe |
| Read OK: | ✔ |
| File size: | 18B3 bytes |
| Load address: | 0000 |
| Exec address: | 0000 |
File contents
A Potted History of Fast Assembler Division by ARBITRARY CONSTANT Divisor ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ I came across a very short assembler routine written by A F Reysenbach several years ago. This used less than a dozen instructions to divide a positive numerator by 10. Given that a traditional Fourier 'shift, compare & conditionally subtract' routine requires around 320 cycles, while an optimised one still requires over 160, Reysenbach's routine was very interesting. Picking this over last year, I realised how the code worked. It used a method analogous to multiplication by a constant via a series of explicit additions with shifts, to encode the constant's bit pattern. Except in this case, it was multiplying by the binary expansion of the reciprocal of 10 & although this does require a few extra checks to prevent intermediate truncation errors destroying the answer, it does work & is still very rapid! I realised it should be possible to use a similar method to divide by arbitrary constant divisor. I established the requirements of such a process & hand coded a few examples. By way of illustration, you'll find routines to divide by 10 & 3 within directory 'Inspire'. However, it still remained a manual job to compile code for each required divisor. Now, the method to construct code to multiply by a constant using repeated shifts & additions can be automated. One near optimal but still simple method is described in the 'Acorn Assembler Release 2' manual in Appendix C, p 187. I set a challenge (in another computer magazine, so no more about that!), to anyone interested, to try to automate the compilation process for division by a constant. Several people had a go at this & one of the best solutions was created by Samuel K.R. Smith. I have since modified his algorithm, making one or two improvements. You'll find details about the process in the accompanying article in the magazine. An implementation of this latest incarnation of the procedure can be found in the Basic assembler program 'FastDiv'. This uses the process to assemble a sequence of routines to divide by a range of constants, & tests each, displaying the current progress & the corresponding code constructed for each divisor. Up to this point, we effectively have a Basic macro to generate division code for arbitrary constant divisor. This is in itself very useful, but it can only be utilised by Basic assembler & the value of the constant must be known when the parent assembler program is compiled. It would be better if the actual process of code generation could itself be written in assembler! This would allow division code to be generated much faster, & from any language, including from within non-Basic programs at run-time. I was going to ask YOU to do this, but in the end I couldn't resist, & had a shot at it myself. 'Generator' contains a data file comprising the final 3�Kb of code required to implement the ARM code division compiler. The assembler source to this is also provided, within 'Generator.s' - this time the source is in Acorn assembler format, rather than Basic assembler. It contains details of the entry & exit conditions to the generator routine. It's rather ironic that this should be compiled using Acorn's DDE Assembler, since the Acorn assembler can't itself utilise the resulting routine as the core to a division code macro, as it provides no means to execute external code at assembly time. You can of course implement the division construction process as a native macro within this Assembler (Samuel's original attempt tried this), but it is cumbersome, limited by the assembler (it doesn't like such large macros) & is slow to execute. Another win to the old Basic assembler, which is very flexible since it puts at one's dispose the entire Basic language for macro implementation via DEFFN. The Basic program 'FastFastDiv' runs the same tests as FastDiv, but using the external machine code Generator routine to compile the code for each divisor - it should produce exactly the same test results as FastDiv. Incidentally, Generator compiles code roughly 200 times faster than the Basic macro! See the magazine for more details. Finally, a new challenge to you, to take this code one stage further. Use it as the core routine to a general purpose assembler division function, to rival the usual Fourier algorithm. The system might work as follows: it would remember the subrouts needed to divide by a range of constants, & when it was asked to divide by an unknown one, it would compile the required code to a buffer, execute it, but crucially, subsequently remember it, in case it is asked to divide by the same value again. The compilation/execution time for a new value would be around 20 times that of a straightforward Fourier division, however subsequent divisions by that same value would execute in roughly 1/6'th of the time of an optimised Fourier routine. So after about 23 calls, we break even & thereon in, make massive speed savings. Consider an image processing application which needs to apply some calculation involving division to the entire image, a group of pixels at a time. If scaling the image, this may involve division by a value which is only known at run time, but which is the same for all of the groups of pixels in the image. This could require division by the one value, for several thousand calculations. In such a situation, the above process would be ideal, providing an increase in speed of approaching 600%! This is just one of many possible computation intensive applications. Note, the decision as to whether a divisor is already known or not would need to be very rapid to make this whole process efficient. You could always permanently remember code for certain divisors, say 1-100 & make the existence check very quick for the last generated routine. As to management of the code fragments, I'd suggest something like the font manager! Allocate an extendible buffer, expandable upto some specified size. Track how often each fragment is used. When space is used up, & another divisor is required, discard the code for the least used divisor (perhaps weighted by how long it was since the last use), to make room for the new routine.
00000000 0a 20 20 41 20 50 6f 74 74 65 64 20 48 69 73 74 |. A Potted Hist| 00000010 6f 72 79 20 6f 66 20 46 61 73 74 20 41 73 73 65 |ory of Fast Asse| 00000020 6d 62 6c 65 72 20 44 69 76 69 73 69 6f 6e 20 62 |mbler Division b| 00000030 79 20 41 52 42 49 54 52 41 52 59 20 43 4f 4e 53 |y ARBITRARY CONS| 00000040 54 41 4e 54 20 44 69 76 69 73 6f 72 0a 20 20 7e |TANT Divisor. ~| 00000050 7e 7e 7e 7e 7e 7e 7e 7e 7e 7e 7e 7e 7e 7e 7e 7e |~~~~~~~~~~~~~~~~| * 00000090 7e 7e 7e 7e 7e 7e 7e 7e 0a 20 20 0a 20 20 49 20 |~~~~~~~~. . I | 000000a0 63 61 6d 65 20 61 63 72 6f 73 73 20 61 20 76 65 |came across a ve| 000000b0 72 79 20 73 68 6f 72 74 20 61 73 73 65 6d 62 6c |ry short assembl| 000000c0 65 72 20 72 6f 75 74 69 6e 65 20 77 72 69 74 74 |er routine writt| 000000d0 65 6e 20 62 79 20 41 20 46 20 52 65 79 73 65 6e |en by A F Reysen| 000000e0 62 61 63 68 0a 73 65 76 65 72 61 6c 20 79 65 61 |bach.several yea| 000000f0 72 73 20 61 67 6f 2e 20 54 68 69 73 20 75 73 65 |rs ago. This use| 00000100 64 20 6c 65 73 73 20 74 68 61 6e 20 61 20 64 6f |d less than a do| 00000110 7a 65 6e 20 69 6e 73 74 72 75 63 74 69 6f 6e 73 |zen instructions| 00000120 20 74 6f 20 64 69 76 69 64 65 20 61 0a 70 6f 73 | to divide a.pos| 00000130 69 74 69 76 65 20 6e 75 6d 65 72 61 74 6f 72 20 |itive numerator | 00000140 62 79 20 31 30 2e 20 47 69 76 65 6e 20 74 68 61 |by 10. Given tha| 00000150 74 20 61 20 74 72 61 64 69 74 69 6f 6e 61 6c 20 |t a traditional | 00000160 46 6f 75 72 69 65 72 20 27 73 68 69 66 74 2c 20 |Fourier 'shift, | 00000170 63 6f 6d 70 61 72 65 20 26 0a 63 6f 6e 64 69 74 |compare &.condit| 00000180 69 6f 6e 61 6c 6c 79 20 73 75 62 74 72 61 63 74 |ionally subtract| 00000190 27 20 72 6f 75 74 69 6e 65 20 72 65 71 75 69 72 |' routine requir| 000001a0 65 73 20 61 72 6f 75 6e 64 20 33 32 30 20 63 79 |es around 320 cy| 000001b0 63 6c 65 73 2c 20 77 68 69 6c 65 20 61 6e 0a 6f |cles, while an.o| 000001c0 70 74 69 6d 69 73 65 64 20 6f 6e 65 20 73 74 69 |ptimised one sti| 000001d0 6c 6c 20 72 65 71 75 69 72 65 73 20 6f 76 65 72 |ll requires over| 000001e0 20 31 36 30 2c 20 52 65 79 73 65 6e 62 61 63 68 | 160, Reysenbach| 000001f0 27 73 20 72 6f 75 74 69 6e 65 20 77 61 73 20 76 |'s routine was v| 00000200 65 72 79 0a 69 6e 74 65 72 65 73 74 69 6e 67 2e |ery.interesting.| 00000210 0a 20 20 0a 20 20 50 69 63 6b 69 6e 67 20 74 68 |. . Picking th| 00000220 69 73 20 6f 76 65 72 20 6c 61 73 74 20 79 65 61 |is over last yea| 00000230 72 2c 20 49 20 72 65 61 6c 69 73 65 64 20 68 6f |r, I realised ho| 00000240 77 20 74 68 65 20 63 6f 64 65 20 77 6f 72 6b 65 |w the code worke| 00000250 64 2e 20 49 74 20 75 73 65 64 20 61 0a 6d 65 74 |d. It used a.met| 00000260 68 6f 64 20 61 6e 61 6c 6f 67 6f 75 73 20 74 6f |hod analogous to| 00000270 20 6d 75 6c 74 69 70 6c 69 63 61 74 69 6f 6e 20 | multiplication | 00000280 62 79 20 61 20 63 6f 6e 73 74 61 6e 74 20 76 69 |by a constant vi| 00000290 61 20 61 20 73 65 72 69 65 73 20 6f 66 20 65 78 |a a series of ex| 000002a0 70 6c 69 63 69 74 0a 61 64 64 69 74 69 6f 6e 73 |plicit.additions| 000002b0 20 77 69 74 68 20 73 68 69 66 74 73 2c 20 74 6f | with shifts, to| 000002c0 20 65 6e 63 6f 64 65 20 74 68 65 20 63 6f 6e 73 | encode the cons| 000002d0 74 61 6e 74 27 73 20 62 69 74 20 70 61 74 74 65 |tant's bit patte| 000002e0 72 6e 2e 20 45 78 63 65 70 74 20 69 6e 20 74 68 |rn. Except in th| 000002f0 69 73 0a 63 61 73 65 2c 20 69 74 20 77 61 73 20 |is.case, it was | 00000300 6d 75 6c 74 69 70 6c 79 69 6e 67 20 62 79 20 74 |multiplying by t| 00000310 68 65 20 62 69 6e 61 72 79 20 65 78 70 61 6e 73 |he binary expans| 00000320 69 6f 6e 20 6f 66 20 74 68 65 20 72 65 63 69 70 |ion of the recip| 00000330 72 6f 63 61 6c 20 6f 66 20 31 30 20 26 0a 61 6c |rocal of 10 &.al| 00000340 74 68 6f 75 67 68 20 74 68 69 73 20 64 6f 65 73 |though this does| 00000350 20 72 65 71 75 69 72 65 20 61 20 66 65 77 20 65 | require a few e| 00000360 78 74 72 61 20 63 68 65 63 6b 73 20 74 6f 20 70 |xtra checks to p| 00000370 72 65 76 65 6e 74 20 69 6e 74 65 72 6d 65 64 69 |revent intermedi| 00000380 61 74 65 0a 74 72 75 6e 63 61 74 69 6f 6e 20 65 |ate.truncation e| 00000390 72 72 6f 72 73 20 64 65 73 74 72 6f 79 69 6e 67 |rrors destroying| 000003a0 20 74 68 65 20 61 6e 73 77 65 72 2c 20 69 74 20 | the answer, it | 000003b0 64 6f 65 73 20 77 6f 72 6b 20 26 20 69 73 20 73 |does work & is s| 000003c0 74 69 6c 6c 20 76 65 72 79 20 72 61 70 69 64 21 |till very rapid!| 000003d0 0a 20 20 0a 20 20 49 20 72 65 61 6c 69 73 65 64 |. . I realised| 000003e0 20 69 74 20 73 68 6f 75 6c 64 20 62 65 20 70 6f | it should be po| 000003f0 73 73 69 62 6c 65 20 74 6f 20 75 73 65 20 61 20 |ssible to use a | 00000400 73 69 6d 69 6c 61 72 20 6d 65 74 68 6f 64 20 74 |similar method t| 00000410 6f 20 64 69 76 69 64 65 20 62 79 0a 61 72 62 69 |o divide by.arbi| 00000420 74 72 61 72 79 20 63 6f 6e 73 74 61 6e 74 20 64 |trary constant d| 00000430 69 76 69 73 6f 72 2e 20 49 20 65 73 74 61 62 6c |ivisor. I establ| 00000440 69 73 68 65 64 20 74 68 65 20 72 65 71 75 69 72 |ished the requir| 00000450 65 6d 65 6e 74 73 20 6f 66 20 73 75 63 68 20 61 |ements of such a| 00000460 20 70 72 6f 63 65 73 73 0a 26 20 68 61 6e 64 20 | process.& hand | 00000470 63 6f 64 65 64 20 61 20 66 65 77 20 65 78 61 6d |coded a few exam| 00000480 70 6c 65 73 2e 20 42 79 20 77 61 79 20 6f 66 20 |ples. By way of | 00000490 69 6c 6c 75 73 74 72 61 74 69 6f 6e 2c 20 79 6f |illustration, yo| 000004a0 75 27 6c 6c 20 66 69 6e 64 20 72 6f 75 74 69 6e |u'll find routin| 000004b0 65 73 20 74 6f 0a 64 69 76 69 64 65 20 62 79 20 |es to.divide by | 000004c0 31 30 20 26 20 33 20 77 69 74 68 69 6e 20 64 69 |10 & 3 within di| 000004d0 72 65 63 74 6f 72 79 20 27 49 6e 73 70 69 72 65 |rectory 'Inspire| 000004e0 27 2e 0a 20 20 0a 20 20 48 6f 77 65 76 65 72 2c |'.. . However,| 000004f0 20 69 74 20 73 74 69 6c 6c 20 72 65 6d 61 69 6e | it still remain| 00000500 65 64 20 61 20 6d 61 6e 75 61 6c 20 6a 6f 62 20 |ed a manual job | 00000510 74 6f 20 63 6f 6d 70 69 6c 65 20 63 6f 64 65 20 |to compile code | 00000520 66 6f 72 20 65 61 63 68 20 72 65 71 75 69 72 65 |for each require| 00000530 64 0a 64 69 76 69 73 6f 72 2e 0a 20 20 0a 20 20 |d.divisor.. . | 00000540 4e 6f 77 2c 20 74 68 65 20 6d 65 74 68 6f 64 20 |Now, the method | 00000550 74 6f 20 63 6f 6e 73 74 72 75 63 74 20 63 6f 64 |to construct cod| 00000560 65 20 74 6f 20 6d 75 6c 74 69 70 6c 79 20 62 79 |e to multiply by| 00000570 20 61 20 63 6f 6e 73 74 61 6e 74 20 75 73 69 6e | a constant usin| 00000580 67 20 72 65 70 65 61 74 65 64 0a 73 68 69 66 74 |g repeated.shift| 00000590 73 20 26 20 61 64 64 69 74 69 6f 6e 73 20 63 61 |s & additions ca| 000005a0 6e 20 62 65 20 61 75 74 6f 6d 61 74 65 64 2e 20 |n be automated. | 000005b0 4f 6e 65 20 6e 65 61 72 20 6f 70 74 69 6d 61 6c |One near optimal| 000005c0 20 62 75 74 20 73 74 69 6c 6c 20 73 69 6d 70 6c | but still simpl| 000005d0 65 0a 6d 65 74 68 6f 64 20 69 73 20 64 65 73 63 |e.method is desc| 000005e0 72 69 62 65 64 20 69 6e 20 74 68 65 20 27 41 63 |ribed in the 'Ac| 000005f0 6f 72 6e 20 41 73 73 65 6d 62 6c 65 72 20 52 65 |orn Assembler Re| 00000600 6c 65 61 73 65 20 32 27 20 6d 61 6e 75 61 6c 20 |lease 2' manual | 00000610 69 6e 20 41 70 70 65 6e 64 69 78 20 43 2c 0a 70 |in Appendix C,.p| 00000620 20 31 38 37 2e 0a 0a 20 20 49 20 73 65 74 20 61 | 187... I set a| 00000630 20 63 68 61 6c 6c 65 6e 67 65 20 28 69 6e 20 61 | challenge (in a| 00000640 6e 6f 74 68 65 72 20 63 6f 6d 70 75 74 65 72 20 |nother computer | 00000650 6d 61 67 61 7a 69 6e 65 2c 20 73 6f 20 6e 6f 20 |magazine, so no | 00000660 6d 6f 72 65 20 61 62 6f 75 74 20 74 68 61 74 21 |more about that!| 00000670 29 2c 0a 74 6f 20 61 6e 79 6f 6e 65 20 69 6e 74 |),.to anyone int| 00000680 65 72 65 73 74 65 64 2c 20 74 6f 20 74 72 79 20 |erested, to try | 00000690 74 6f 20 61 75 74 6f 6d 61 74 65 20 74 68 65 20 |to automate the | 000006a0 63 6f 6d 70 69 6c 61 74 69 6f 6e 20 70 72 6f 63 |compilation proc| 000006b0 65 73 73 20 66 6f 72 0a 64 69 76 69 73 69 6f 6e |ess for.division| 000006c0 20 62 79 20 61 20 63 6f 6e 73 74 61 6e 74 2e 20 | by a constant. | 000006d0 53 65 76 65 72 61 6c 20 70 65 6f 70 6c 65 20 68 |Several people h| 000006e0 61 64 20 61 20 67 6f 20 61 74 20 74 68 69 73 20 |ad a go at this | 000006f0 26 20 6f 6e 65 20 6f 66 20 74 68 65 20 62 65 73 |& one of the bes| 00000700 74 0a 73 6f 6c 75 74 69 6f 6e 73 20 77 61 73 20 |t.solutions was | 00000710 63 72 65 61 74 65 64 20 62 79 20 53 61 6d 75 65 |created by Samue| 00000720 6c 20 4b 2e 52 2e 20 53 6d 69 74 68 2e 0a 0a 20 |l K.R. Smith... | 00000730 20 49 20 68 61 76 65 20 73 69 6e 63 65 20 6d 6f | I have since mo| 00000740 64 69 66 69 65 64 20 68 69 73 20 61 6c 67 6f 72 |dified his algor| 00000750 69 74 68 6d 2c 20 6d 61 6b 69 6e 67 20 6f 6e 65 |ithm, making one| 00000760 20 6f 72 20 74 77 6f 20 69 6d 70 72 6f 76 65 6d | or two improvem| 00000770 65 6e 74 73 2e 0a 59 6f 75 27 6c 6c 20 66 69 6e |ents..You'll fin| 00000780 64 20 64 65 74 61 69 6c 73 20 61 62 6f 75 74 20 |d details about | 00000790 74 68 65 20 70 72 6f 63 65 73 73 20 69 6e 20 74 |the process in t| 000007a0 68 65 20 61 63 63 6f 6d 70 61 6e 79 69 6e 67 20 |he accompanying | 000007b0 61 72 74 69 63 6c 65 20 69 6e 20 74 68 65 0a 6d |article in the.m| 000007c0 61 67 61 7a 69 6e 65 2e 20 41 6e 20 69 6d 70 6c |agazine. An impl| 000007d0 65 6d 65 6e 74 61 74 69 6f 6e 20 6f 66 20 74 68 |ementation of th| 000007e0 69 73 20 6c 61 74 65 73 74 20 69 6e 63 61 72 6e |is latest incarn| 000007f0 61 74 69 6f 6e 20 6f 66 20 74 68 65 20 70 72 6f |ation of the pro| 00000800 63 65 64 75 72 65 20 63 61 6e 0a 62 65 20 66 6f |cedure can.be fo| 00000810 75 6e 64 20 69 6e 20 74 68 65 20 42 61 73 69 63 |und in the Basic| 00000820 20 61 73 73 65 6d 62 6c 65 72 20 70 72 6f 67 72 | assembler progr| 00000830 61 6d 20 27 46 61 73 74 44 69 76 27 2e 20 54 68 |am 'FastDiv'. Th| 00000840 69 73 20 75 73 65 73 20 74 68 65 20 70 72 6f 63 |is uses the proc| 00000850 65 73 73 20 74 6f 0a 61 73 73 65 6d 62 6c 65 20 |ess to.assemble | 00000860 61 20 73 65 71 75 65 6e 63 65 20 6f 66 20 72 6f |a sequence of ro| 00000870 75 74 69 6e 65 73 20 74 6f 20 64 69 76 69 64 65 |utines to divide| 00000880 20 62 79 20 61 20 72 61 6e 67 65 20 6f 66 20 63 | by a range of c| 00000890 6f 6e 73 74 61 6e 74 73 2c 20 26 20 74 65 73 74 |onstants, & test| 000008a0 73 0a 65 61 63 68 2c 20 64 69 73 70 6c 61 79 69 |s.each, displayi| 000008b0 6e 67 20 74 68 65 20 63 75 72 72 65 6e 74 20 70 |ng the current p| 000008c0 72 6f 67 72 65 73 73 20 26 20 74 68 65 20 63 6f |rogress & the co| 000008d0 72 72 65 73 70 6f 6e 64 69 6e 67 20 63 6f 64 65 |rresponding code| 000008e0 20 63 6f 6e 73 74 72 75 63 74 65 64 0a 66 6f 72 | constructed.for| 000008f0 20 65 61 63 68 20 64 69 76 69 73 6f 72 2e 0a 0a | each divisor...| 00000900 20 20 55 70 20 74 6f 20 74 68 69 73 20 70 6f 69 | Up to this poi| 00000910 6e 74 2c 20 77 65 20 65 66 66 65 63 74 69 76 65 |nt, we effective| 00000920 6c 79 20 68 61 76 65 20 61 20 42 61 73 69 63 20 |ly have a Basic | 00000930 6d 61 63 72 6f 20 74 6f 20 67 65 6e 65 72 61 74 |macro to generat| 00000940 65 20 64 69 76 69 73 69 6f 6e 0a 63 6f 64 65 20 |e division.code | 00000950 66 6f 72 20 61 72 62 69 74 72 61 72 79 20 63 6f |for arbitrary co| 00000960 6e 73 74 61 6e 74 20 64 69 76 69 73 6f 72 2e 20 |nstant divisor. | 00000970 54 68 69 73 20 69 73 20 69 6e 20 69 74 73 65 6c |This is in itsel| 00000980 66 20 76 65 72 79 20 75 73 65 66 75 6c 2c 20 62 |f very useful, b| 00000990 75 74 20 69 74 0a 63 61 6e 20 6f 6e 6c 79 20 62 |ut it.can only b| 000009a0 65 20 75 74 69 6c 69 73 65 64 20 62 79 20 42 61 |e utilised by Ba| 000009b0 73 69 63 20 61 73 73 65 6d 62 6c 65 72 20 26 20 |sic assembler & | 000009c0 74 68 65 20 76 61 6c 75 65 20 6f 66 20 74 68 65 |the value of the| 000009d0 20 63 6f 6e 73 74 61 6e 74 20 6d 75 73 74 20 62 | constant must b| 000009e0 65 0a 6b 6e 6f 77 6e 20 77 68 65 6e 20 74 68 65 |e.known when the| 000009f0 20 70 61 72 65 6e 74 20 61 73 73 65 6d 62 6c 65 | parent assemble| 00000a00 72 20 70 72 6f 67 72 61 6d 20 69 73 20 63 6f 6d |r program is com| 00000a10 70 69 6c 65 64 2e 0a 0a 20 20 49 74 20 77 6f 75 |piled... It wou| 00000a20 6c 64 20 62 65 20 62 65 74 74 65 72 20 69 66 20 |ld be better if | 00000a30 74 68 65 20 61 63 74 75 61 6c 20 70 72 6f 63 65 |the actual proce| 00000a40 73 73 20 6f 66 20 63 6f 64 65 20 67 65 6e 65 72 |ss of code gener| 00000a50 61 74 69 6f 6e 20 63 6f 75 6c 64 20 69 74 73 65 |ation could itse| 00000a60 6c 66 0a 62 65 20 77 72 69 74 74 65 6e 20 69 6e |lf.be written in| 00000a70 20 61 73 73 65 6d 62 6c 65 72 21 20 54 68 69 73 | assembler! This| 00000a80 20 77 6f 75 6c 64 20 61 6c 6c 6f 77 20 64 69 76 | would allow div| 00000a90 69 73 69 6f 6e 20 63 6f 64 65 20 74 6f 20 62 65 |ision code to be| 00000aa0 20 67 65 6e 65 72 61 74 65 64 20 6d 75 63 68 0a | generated much.| 00000ab0 66 61 73 74 65 72 2c 20 26 20 66 72 6f 6d 20 61 |faster, & from a| 00000ac0 6e 79 20 6c 61 6e 67 75 61 67 65 2c 20 69 6e 63 |ny language, inc| 00000ad0 6c 75 64 69 6e 67 20 66 72 6f 6d 20 77 69 74 68 |luding from with| 00000ae0 69 6e 20 6e 6f 6e 2d 42 61 73 69 63 20 70 72 6f |in non-Basic pro| 00000af0 67 72 61 6d 73 20 61 74 0a 72 75 6e 2d 74 69 6d |grams at.run-tim| 00000b00 65 2e 0a 0a 20 20 49 20 77 61 73 20 67 6f 69 6e |e... I was goin| 00000b10 67 20 74 6f 20 61 73 6b 20 59 4f 55 20 74 6f 20 |g to ask YOU to | 00000b20 64 6f 20 74 68 69 73 2c 20 62 75 74 20 69 6e 20 |do this, but in | 00000b30 74 68 65 20 65 6e 64 20 49 20 63 6f 75 6c 64 6e |the end I couldn| 00000b40 27 74 20 72 65 73 69 73 74 2c 20 26 20 68 61 64 |'t resist, & had| 00000b50 0a 61 20 73 68 6f 74 20 61 74 20 69 74 20 6d 79 |.a shot at it my| 00000b60 73 65 6c 66 2e 20 27 47 65 6e 65 72 61 74 6f 72 |self. 'Generator| 00000b70 27 20 63 6f 6e 74 61 69 6e 73 20 61 20 64 61 74 |' contains a dat| 00000b80 61 20 66 69 6c 65 20 63 6f 6d 70 72 69 73 69 6e |a file comprisin| 00000b90 67 20 74 68 65 20 66 69 6e 61 6c 0a 33 bd 4b 62 |g the final.3.Kb| 00000ba0 20 6f 66 20 63 6f 64 65 20 72 65 71 75 69 72 65 | of code require| 00000bb0 64 20 74 6f 20 69 6d 70 6c 65 6d 65 6e 74 20 74 |d to implement t| 00000bc0 68 65 20 41 52 4d 20 63 6f 64 65 20 64 69 76 69 |he ARM code divi| 00000bd0 73 69 6f 6e 20 63 6f 6d 70 69 6c 65 72 2e 20 54 |sion compiler. T| 00000be0 68 65 0a 61 73 73 65 6d 62 6c 65 72 20 73 6f 75 |he.assembler sou| 00000bf0 72 63 65 20 74 6f 20 74 68 69 73 20 69 73 20 61 |rce to this is a| 00000c00 6c 73 6f 20 70 72 6f 76 69 64 65 64 2c 20 77 69 |lso provided, wi| 00000c10 74 68 69 6e 20 27 47 65 6e 65 72 61 74 6f 72 2e |thin 'Generator.| 00000c20 73 27 20 2d 20 74 68 69 73 20 74 69 6d 65 0a 74 |s' - this time.t| 00000c30 68 65 20 73 6f 75 72 63 65 20 69 73 20 69 6e 20 |he source is in | 00000c40 41 63 6f 72 6e 20 61 73 73 65 6d 62 6c 65 72 20 |Acorn assembler | 00000c50 66 6f 72 6d 61 74 2c 20 72 61 74 68 65 72 20 74 |format, rather t| 00000c60 68 61 6e 20 42 61 73 69 63 20 61 73 73 65 6d 62 |han Basic assemb| 00000c70 6c 65 72 2e 20 49 74 0a 63 6f 6e 74 61 69 6e 73 |ler. It.contains| 00000c80 20 64 65 74 61 69 6c 73 20 6f 66 20 74 68 65 20 | details of the | 00000c90 65 6e 74 72 79 20 26 20 65 78 69 74 20 63 6f 6e |entry & exit con| 00000ca0 64 69 74 69 6f 6e 73 20 74 6f 20 74 68 65 20 67 |ditions to the g| 00000cb0 65 6e 65 72 61 74 6f 72 20 72 6f 75 74 69 6e 65 |enerator routine| 00000cc0 2e 0a 0a 20 20 49 74 27 73 20 72 61 74 68 65 72 |... It's rather| 00000cd0 20 69 72 6f 6e 69 63 20 74 68 61 74 20 74 68 69 | ironic that thi| 00000ce0 73 20 73 68 6f 75 6c 64 20 62 65 20 63 6f 6d 70 |s should be comp| 00000cf0 69 6c 65 64 20 75 73 69 6e 67 20 41 63 6f 72 6e |iled using Acorn| 00000d00 27 73 20 44 44 45 0a 41 73 73 65 6d 62 6c 65 72 |'s DDE.Assembler| 00000d10 2c 20 73 69 6e 63 65 20 74 68 65 20 41 63 6f 72 |, since the Acor| 00000d20 6e 20 61 73 73 65 6d 62 6c 65 72 20 63 61 6e 27 |n assembler can'| 00000d30 74 20 69 74 73 65 6c 66 20 75 74 69 6c 69 73 65 |t itself utilise| 00000d40 20 74 68 65 20 72 65 73 75 6c 74 69 6e 67 0a 72 | the resulting.r| 00000d50 6f 75 74 69 6e 65 20 61 73 20 74 68 65 20 63 6f |outine as the co| 00000d60 72 65 20 74 6f 20 61 20 64 69 76 69 73 69 6f 6e |re to a division| 00000d70 20 63 6f 64 65 20 6d 61 63 72 6f 2c 20 61 73 20 | code macro, as | 00000d80 69 74 20 70 72 6f 76 69 64 65 73 20 6e 6f 20 6d |it provides no m| 00000d90 65 61 6e 73 20 74 6f 0a 65 78 65 63 75 74 65 20 |eans to.execute | 00000da0 65 78 74 65 72 6e 61 6c 20 63 6f 64 65 20 61 74 |external code at| 00000db0 20 61 73 73 65 6d 62 6c 79 20 74 69 6d 65 2e 20 | assembly time. | 00000dc0 59 6f 75 20 63 61 6e 20 6f 66 20 63 6f 75 72 73 |You can of cours| 00000dd0 65 20 69 6d 70 6c 65 6d 65 6e 74 20 74 68 65 0a |e implement the.| 00000de0 64 69 76 69 73 69 6f 6e 20 63 6f 6e 73 74 72 75 |division constru| 00000df0 63 74 69 6f 6e 20 70 72 6f 63 65 73 73 20 61 73 |ction process as| 00000e00 20 61 20 6e 61 74 69 76 65 20 6d 61 63 72 6f 20 | a native macro | 00000e10 77 69 74 68 69 6e 20 74 68 69 73 20 41 73 73 65 |within this Asse| 00000e20 6d 62 6c 65 72 0a 28 53 61 6d 75 65 6c 27 73 20 |mbler.(Samuel's | 00000e30 6f 72 69 67 69 6e 61 6c 20 61 74 74 65 6d 70 74 |original attempt| 00000e40 20 74 72 69 65 64 20 74 68 69 73 29 2c 20 62 75 | tried this), bu| 00000e50 74 20 69 74 20 69 73 20 63 75 6d 62 65 72 73 6f |t it is cumberso| 00000e60 6d 65 2c 20 6c 69 6d 69 74 65 64 20 62 79 20 74 |me, limited by t| 00000e70 68 65 0a 61 73 73 65 6d 62 6c 65 72 20 28 69 74 |he.assembler (it| 00000e80 20 64 6f 65 73 6e 27 74 20 6c 69 6b 65 20 73 75 | doesn't like su| 00000e90 63 68 20 6c 61 72 67 65 20 6d 61 63 72 6f 73 29 |ch large macros)| 00000ea0 20 26 20 69 73 20 73 6c 6f 77 20 74 6f 20 65 78 | & is slow to ex| 00000eb0 65 63 75 74 65 2e 20 41 6e 6f 74 68 65 72 0a 77 |ecute. Another.w| 00000ec0 69 6e 20 74 6f 20 74 68 65 20 6f 6c 64 20 42 61 |in to the old Ba| 00000ed0 73 69 63 20 61 73 73 65 6d 62 6c 65 72 2c 20 77 |sic assembler, w| 00000ee0 68 69 63 68 20 69 73 20 76 65 72 79 20 66 6c 65 |hich is very fle| 00000ef0 78 69 62 6c 65 20 73 69 6e 63 65 20 69 74 20 70 |xible since it p| 00000f00 75 74 73 20 61 74 0a 6f 6e 65 27 73 20 64 69 73 |uts at.one's dis| 00000f10 70 6f 73 65 20 74 68 65 20 65 6e 74 69 72 65 20 |pose the entire | 00000f20 42 61 73 69 63 20 6c 61 6e 67 75 61 67 65 20 66 |Basic language f| 00000f30 6f 72 20 6d 61 63 72 6f 20 69 6d 70 6c 65 6d 65 |or macro impleme| 00000f40 6e 74 61 74 69 6f 6e 20 76 69 61 20 44 45 46 46 |ntation via DEFF| 00000f50 4e 2e 0a 0a 20 20 54 68 65 20 42 61 73 69 63 20 |N... The Basic | 00000f60 70 72 6f 67 72 61 6d 20 27 46 61 73 74 46 61 73 |program 'FastFas| 00000f70 74 44 69 76 27 20 72 75 6e 73 20 74 68 65 20 73 |tDiv' runs the s| 00000f80 61 6d 65 20 74 65 73 74 73 20 61 73 20 46 61 73 |ame tests as Fas| 00000f90 74 44 69 76 2c 20 62 75 74 20 75 73 69 6e 67 0a |tDiv, but using.| 00000fa0 74 68 65 20 65 78 74 65 72 6e 61 6c 20 6d 61 63 |the external mac| 00000fb0 68 69 6e 65 20 63 6f 64 65 20 47 65 6e 65 72 61 |hine code Genera| 00000fc0 74 6f 72 20 72 6f 75 74 69 6e 65 20 74 6f 20 63 |tor routine to c| 00000fd0 6f 6d 70 69 6c 65 20 74 68 65 20 63 6f 64 65 20 |ompile the code | 00000fe0 66 6f 72 20 65 61 63 68 0a 64 69 76 69 73 6f 72 |for each.divisor| 00000ff0 20 2d 20 69 74 20 73 68 6f 75 6c 64 20 70 72 6f | - it should pro| 00001000 64 75 63 65 20 65 78 61 63 74 6c 79 20 74 68 65 |duce exactly the| 00001010 20 73 61 6d 65 20 74 65 73 74 20 72 65 73 75 6c | same test resul| 00001020 74 73 20 61 73 20 46 61 73 74 44 69 76 2e 0a 49 |ts as FastDiv..I| 00001030 6e 63 69 64 65 6e 74 61 6c 6c 79 2c 20 47 65 6e |ncidentally, Gen| 00001040 65 72 61 74 6f 72 20 63 6f 6d 70 69 6c 65 73 20 |erator compiles | 00001050 63 6f 64 65 20 72 6f 75 67 68 6c 79 20 32 30 30 |code roughly 200| 00001060 20 74 69 6d 65 73 20 66 61 73 74 65 72 20 74 68 | times faster th| 00001070 61 6e 20 74 68 65 0a 42 61 73 69 63 20 6d 61 63 |an the.Basic mac| 00001080 72 6f 21 20 53 65 65 20 74 68 65 20 6d 61 67 61 |ro! See the maga| 00001090 7a 69 6e 65 20 66 6f 72 20 6d 6f 72 65 20 64 65 |zine for more de| 000010a0 74 61 69 6c 73 2e 0a 0a 20 20 46 69 6e 61 6c 6c |tails... Finall| 000010b0 79 2c 20 61 20 6e 65 77 20 63 68 61 6c 6c 65 6e |y, a new challen| 000010c0 67 65 20 74 6f 20 79 6f 75 2c 20 74 6f 20 74 61 |ge to you, to ta| 000010d0 6b 65 20 74 68 69 73 20 63 6f 64 65 20 6f 6e 65 |ke this code one| 000010e0 20 73 74 61 67 65 20 66 75 72 74 68 65 72 2e 20 | stage further. | 000010f0 55 73 65 0a 69 74 20 61 73 20 74 68 65 20 63 6f |Use.it as the co| 00001100 72 65 20 72 6f 75 74 69 6e 65 20 74 6f 20 61 20 |re routine to a | 00001110 67 65 6e 65 72 61 6c 20 70 75 72 70 6f 73 65 20 |general purpose | 00001120 61 73 73 65 6d 62 6c 65 72 20 64 69 76 69 73 69 |assembler divisi| 00001130 6f 6e 20 66 75 6e 63 74 69 6f 6e 2c 20 74 6f 0a |on function, to.| 00001140 72 69 76 61 6c 20 74 68 65 20 75 73 75 61 6c 20 |rival the usual | 00001150 46 6f 75 72 69 65 72 20 61 6c 67 6f 72 69 74 68 |Fourier algorith| 00001160 6d 2e 0a 0a 20 20 54 68 65 20 73 79 73 74 65 6d |m... The system| 00001170 20 6d 69 67 68 74 20 77 6f 72 6b 20 61 73 20 66 | might work as f| 00001180 6f 6c 6c 6f 77 73 3a 20 69 74 20 77 6f 75 6c 64 |ollows: it would| 00001190 20 72 65 6d 65 6d 62 65 72 20 74 68 65 20 73 75 | remember the su| 000011a0 62 72 6f 75 74 73 20 6e 65 65 64 65 64 20 74 6f |brouts needed to| 000011b0 0a 64 69 76 69 64 65 20 62 79 20 61 20 72 61 6e |.divide by a ran| 000011c0 67 65 20 6f 66 20 63 6f 6e 73 74 61 6e 74 73 2c |ge of constants,| 000011d0 20 26 20 77 68 65 6e 20 69 74 20 77 61 73 20 61 | & when it was a| 000011e0 73 6b 65 64 20 74 6f 20 64 69 76 69 64 65 20 62 |sked to divide b| 000011f0 79 20 61 6e 20 75 6e 6b 6e 6f 77 6e 0a 6f 6e 65 |y an unknown.one| 00001200 2c 20 69 74 20 77 6f 75 6c 64 20 63 6f 6d 70 69 |, it would compi| 00001210 6c 65 20 74 68 65 20 72 65 71 75 69 72 65 64 20 |le the required | 00001220 63 6f 64 65 20 74 6f 20 61 20 62 75 66 66 65 72 |code to a buffer| 00001230 2c 20 65 78 65 63 75 74 65 20 69 74 2c 20 62 75 |, execute it, bu| 00001240 74 0a 63 72 75 63 69 61 6c 6c 79 2c 20 73 75 62 |t.crucially, sub| 00001250 73 65 71 75 65 6e 74 6c 79 20 72 65 6d 65 6d 62 |sequently rememb| 00001260 65 72 20 69 74 2c 20 69 6e 20 63 61 73 65 20 69 |er it, in case i| 00001270 74 20 69 73 20 61 73 6b 65 64 20 74 6f 20 64 69 |t is asked to di| 00001280 76 69 64 65 20 62 79 20 74 68 65 0a 73 61 6d 65 |vide by the.same| 00001290 20 76 61 6c 75 65 20 61 67 61 69 6e 2e 20 54 68 | value again. Th| 000012a0 65 20 63 6f 6d 70 69 6c 61 74 69 6f 6e 2f 65 78 |e compilation/ex| 000012b0 65 63 75 74 69 6f 6e 20 74 69 6d 65 20 66 6f 72 |ecution time for| 000012c0 20 61 20 6e 65 77 20 76 61 6c 75 65 20 77 6f 75 | a new value wou| 000012d0 6c 64 20 62 65 0a 61 72 6f 75 6e 64 20 32 30 20 |ld be.around 20 | 000012e0 74 69 6d 65 73 20 74 68 61 74 20 6f 66 20 61 20 |times that of a | 000012f0 73 74 72 61 69 67 68 74 66 6f 72 77 61 72 64 20 |straightforward | 00001300 46 6f 75 72 69 65 72 20 64 69 76 69 73 69 6f 6e |Fourier division| 00001310 2c 20 68 6f 77 65 76 65 72 0a 73 75 62 73 65 71 |, however.subseq| 00001320 75 65 6e 74 20 64 69 76 69 73 69 6f 6e 73 20 62 |uent divisions b| 00001330 79 20 74 68 61 74 20 73 61 6d 65 20 76 61 6c 75 |y that same valu| 00001340 65 20 77 6f 75 6c 64 20 65 78 65 63 75 74 65 20 |e would execute | 00001350 69 6e 20 72 6f 75 67 68 6c 79 20 31 2f 36 27 74 |in roughly 1/6't| 00001360 68 20 6f 66 0a 74 68 65 20 74 69 6d 65 20 6f 66 |h of.the time of| 00001370 20 61 6e 20 6f 70 74 69 6d 69 73 65 64 20 46 6f | an optimised Fo| 00001380 75 72 69 65 72 20 72 6f 75 74 69 6e 65 2e 20 53 |urier routine. S| 00001390 6f 20 61 66 74 65 72 20 61 62 6f 75 74 20 32 33 |o after about 23| 000013a0 20 63 61 6c 6c 73 2c 20 77 65 20 62 72 65 61 6b | calls, we break| 000013b0 0a 65 76 65 6e 20 26 20 74 68 65 72 65 6f 6e 20 |.even & thereon | 000013c0 69 6e 2c 20 6d 61 6b 65 20 6d 61 73 73 69 76 65 |in, make massive| 000013d0 20 73 70 65 65 64 20 73 61 76 69 6e 67 73 2e 0a | speed savings..| 000013e0 0a 20 20 43 6f 6e 73 69 64 65 72 20 61 6e 20 69 |. Consider an i| 000013f0 6d 61 67 65 20 70 72 6f 63 65 73 73 69 6e 67 20 |mage processing | 00001400 61 70 70 6c 69 63 61 74 69 6f 6e 20 77 68 69 63 |application whic| 00001410 68 20 6e 65 65 64 73 20 74 6f 20 61 70 70 6c 79 |h needs to apply| 00001420 20 73 6f 6d 65 0a 63 61 6c 63 75 6c 61 74 69 6f | some.calculatio| 00001430 6e 20 69 6e 76 6f 6c 76 69 6e 67 20 64 69 76 69 |n involving divi| 00001440 73 69 6f 6e 20 74 6f 20 74 68 65 20 65 6e 74 69 |sion to the enti| 00001450 72 65 20 69 6d 61 67 65 2c 20 61 20 67 72 6f 75 |re image, a grou| 00001460 70 20 6f 66 20 70 69 78 65 6c 73 20 61 74 20 61 |p of pixels at a| 00001470 0a 74 69 6d 65 2e 20 49 66 20 73 63 61 6c 69 6e |.time. If scalin| 00001480 67 20 74 68 65 20 69 6d 61 67 65 2c 20 74 68 69 |g the image, thi| 00001490 73 20 6d 61 79 20 69 6e 76 6f 6c 76 65 20 64 69 |s may involve di| 000014a0 76 69 73 69 6f 6e 20 62 79 20 61 20 76 61 6c 75 |vision by a valu| 000014b0 65 20 77 68 69 63 68 20 69 73 0a 6f 6e 6c 79 20 |e which is.only | 000014c0 6b 6e 6f 77 6e 20 61 74 20 72 75 6e 20 74 69 6d |known at run tim| 000014d0 65 2c 20 62 75 74 20 77 68 69 63 68 20 69 73 20 |e, but which is | 000014e0 74 68 65 20 73 61 6d 65 20 66 6f 72 20 61 6c 6c |the same for all| 000014f0 20 6f 66 20 74 68 65 20 67 72 6f 75 70 73 20 6f | of the groups o| 00001500 66 0a 70 69 78 65 6c 73 20 69 6e 20 74 68 65 20 |f.pixels in the | 00001510 69 6d 61 67 65 2e 20 54 68 69 73 20 63 6f 75 6c |image. This coul| 00001520 64 20 72 65 71 75 69 72 65 20 64 69 76 69 73 69 |d require divisi| 00001530 6f 6e 20 62 79 20 74 68 65 20 6f 6e 65 20 76 61 |on by the one va| 00001540 6c 75 65 2c 20 66 6f 72 0a 73 65 76 65 72 61 6c |lue, for.several| 00001550 20 74 68 6f 75 73 61 6e 64 20 63 61 6c 63 75 6c | thousand calcul| 00001560 61 74 69 6f 6e 73 2e 20 49 6e 20 73 75 63 68 20 |ations. In such | 00001570 61 20 73 69 74 75 61 74 69 6f 6e 2c 20 74 68 65 |a situation, the| 00001580 20 61 62 6f 76 65 20 70 72 6f 63 65 73 73 20 77 | above process w| 00001590 6f 75 6c 64 0a 62 65 20 69 64 65 61 6c 2c 20 70 |ould.be ideal, p| 000015a0 72 6f 76 69 64 69 6e 67 20 61 6e 20 69 6e 63 72 |roviding an incr| 000015b0 65 61 73 65 20 69 6e 20 73 70 65 65 64 20 6f 66 |ease in speed of| 000015c0 20 61 70 70 72 6f 61 63 68 69 6e 67 20 36 30 30 | approaching 600| 000015d0 25 21 20 54 68 69 73 20 69 73 20 6a 75 73 74 0a |%! This is just.| 000015e0 6f 6e 65 20 6f 66 20 6d 61 6e 79 20 70 6f 73 73 |one of many poss| 000015f0 69 62 6c 65 20 63 6f 6d 70 75 74 61 74 69 6f 6e |ible computation| 00001600 20 69 6e 74 65 6e 73 69 76 65 20 61 70 70 6c 69 | intensive appli| 00001610 63 61 74 69 6f 6e 73 2e 0a 0a 20 20 4e 6f 74 65 |cations... Note| 00001620 2c 20 74 68 65 20 64 65 63 69 73 69 6f 6e 20 61 |, the decision a| 00001630 73 20 74 6f 20 77 68 65 74 68 65 72 20 61 20 64 |s to whether a d| 00001640 69 76 69 73 6f 72 20 69 73 20 61 6c 72 65 61 64 |ivisor is alread| 00001650 79 20 6b 6e 6f 77 6e 20 6f 72 20 6e 6f 74 20 77 |y known or not w| 00001660 6f 75 6c 64 0a 6e 65 65 64 20 74 6f 20 62 65 20 |ould.need to be | 00001670 76 65 72 79 20 72 61 70 69 64 20 74 6f 20 6d 61 |very rapid to ma| 00001680 6b 65 20 74 68 69 73 20 77 68 6f 6c 65 20 70 72 |ke this whole pr| 00001690 6f 63 65 73 73 20 65 66 66 69 63 69 65 6e 74 2e |ocess efficient.| 000016a0 20 59 6f 75 20 63 6f 75 6c 64 20 61 6c 77 61 79 | You could alway| 000016b0 73 0a 70 65 72 6d 61 6e 65 6e 74 6c 79 20 72 65 |s.permanently re| 000016c0 6d 65 6d 62 65 72 20 63 6f 64 65 20 66 6f 72 20 |member code for | 000016d0 63 65 72 74 61 69 6e 20 64 69 76 69 73 6f 72 73 |certain divisors| 000016e0 2c 20 73 61 79 20 31 2d 31 30 30 20 26 20 6d 61 |, say 1-100 & ma| 000016f0 6b 65 20 74 68 65 0a 65 78 69 73 74 65 6e 63 65 |ke the.existence| 00001700 20 63 68 65 63 6b 20 76 65 72 79 20 71 75 69 63 | check very quic| 00001710 6b 20 66 6f 72 20 74 68 65 20 6c 61 73 74 20 67 |k for the last g| 00001720 65 6e 65 72 61 74 65 64 20 72 6f 75 74 69 6e 65 |enerated routine| 00001730 2e 0a 0a 20 20 41 73 20 74 6f 20 6d 61 6e 61 67 |... As to manag| 00001740 65 6d 65 6e 74 20 6f 66 20 74 68 65 20 63 6f 64 |ement of the cod| 00001750 65 20 66 72 61 67 6d 65 6e 74 73 2c 20 49 27 64 |e fragments, I'd| 00001760 20 73 75 67 67 65 73 74 20 73 6f 6d 65 74 68 69 | suggest somethi| 00001770 6e 67 20 6c 69 6b 65 20 74 68 65 0a 66 6f 6e 74 |ng like the.font| 00001780 20 6d 61 6e 61 67 65 72 21 20 41 6c 6c 6f 63 61 | manager! Alloca| 00001790 74 65 20 61 6e 20 65 78 74 65 6e 64 69 62 6c 65 |te an extendible| 000017a0 20 62 75 66 66 65 72 2c 20 65 78 70 61 6e 64 61 | buffer, expanda| 000017b0 62 6c 65 20 75 70 74 6f 20 73 6f 6d 65 20 73 70 |ble upto some sp| 000017c0 65 63 69 66 69 65 64 0a 73 69 7a 65 2e 20 54 72 |ecified.size. Tr| 000017d0 61 63 6b 20 68 6f 77 20 6f 66 74 65 6e 20 65 61 |ack how often ea| 000017e0 63 68 20 66 72 61 67 6d 65 6e 74 20 69 73 20 75 |ch fragment is u| 000017f0 73 65 64 2e 20 57 68 65 6e 20 73 70 61 63 65 20 |sed. When space | 00001800 69 73 20 75 73 65 64 20 75 70 2c 20 26 0a 61 6e |is used up, &.an| 00001810 6f 74 68 65 72 20 64 69 76 69 73 6f 72 20 69 73 |other divisor is| 00001820 20 72 65 71 75 69 72 65 64 2c 20 64 69 73 63 61 | required, disca| 00001830 72 64 20 74 68 65 20 63 6f 64 65 20 66 6f 72 20 |rd the code for | 00001840 74 68 65 20 6c 65 61 73 74 20 75 73 65 64 20 64 |the least used d| 00001850 69 76 69 73 6f 72 0a 28 70 65 72 68 61 70 73 20 |ivisor.(perhaps | 00001860 77 65 69 67 68 74 65 64 20 62 79 20 68 6f 77 20 |weighted by how | 00001870 6c 6f 6e 67 20 69 74 20 77 61 73 20 73 69 6e 63 |long it was sinc| 00001880 65 20 74 68 65 20 6c 61 73 74 20 75 73 65 29 2c |e the last use),| 00001890 20 74 6f 20 6d 61 6b 65 20 72 6f 6f 6d 20 66 6f | to make room fo| 000018a0 72 0a 74 68 65 20 6e 65 77 20 72 6f 75 74 69 6e |r.the new routin| 000018b0 65 2e 0a |e..| 000018b3
.