How to allocate scratchpad memory?
Al Borowski
What is the best way reserve a large-ish (>32K) chunk of RAM for working?
What I would like to do is:
1) Use SysRPL / Emulated Saturn assembly to reserve a chunk of memory to
play with.
2) Jump to ARM land, and do something that requires a decent amount of
RAM for working.
3) Finally, return some of the allocated RAM to the system. The rest
will be used as an object to be placed on the stack, so I need to tell
the OS not to override it. This could be done in SysRPL or assembly.
I've searched google groups and havn't found any decent answers. What
I'd like to know is, how do I reserve RAM and free parts of it later?
Also how do I mark areas of RAM as 'in use by an object'?
Are there any pitfalls involving the Garbage Collector?
If someone could just give me a link or an explanation I'd be grateful.
Thanks,
Al
Veli-Pekka Nousiainen
news:404aef3d$0$22506$5a62...@freenews.iinet.net.au...
While I Know almost nothing about SysRPL
a string comes into mind, either in Stack or in a (hidden variable)
but what if memory moves?
Maybe you could force GC first.
[VPN]
Al Borowski
My code needs to have some free room for working, and also return a
string or integer.
I'd like to use MAKE$ to create a 32kb string, use the last 16kb as
scratch space (so it gets filled with junk) - Then I'd use the first
16kb or so to store the result. Finally I'd alter the type/size fields
so only the first part of the old string (that which contains the
result) are returned.
To put it graphically...
[ABCDEFGHI] <-- The string as it was created, size 9, type string
[2d4f5tftg] <-- The 'string' being used as working room during the ARM
code. Size is still set to 9, type is set to string. Contents is junk as
far as the HP is concerned.
[1234hdfgy] <-- The 'string' after my code completes. The type is now
set to Integer, Length 4.
I'd want 1234 to be on the stack in this example, and not corrupted by
the garbage on the end. I also don't want the junk data wasting memory.
Will this work? Or am I totally lost?
thanks,
Al
Xorxar
> I'd want 1234 to be on the stack in this example, and not corrupted by
> the garbage on the end. I also don't want the junk data wasting memory.
I think, in this case, that it will work, but the nibbles unused will not be
freed. Your 32kb will always be reserved, although there is nothing
interesting in most of them.
--
Xorxar
Jonathan Busby
::
GARBAGE ( Make sure the maximum amount of memory is free. )
CODE
GOSBVL =SAVPTR
...
GOSBVL =MAKERAM$ Allocate all available memory (minus 5
* nibbles ) to a string . String
* prologue address is returned in R0.
*
...
* Here, D0 points one nibble past the end of the data that you
* want the final string to contain. R0 points to the
* prologue.
GOSBVL =Shrink$ * Truncate all the string data
* starting at D0 and resize
* accordingly. Unused memory is
* reclaimed by the OS.
GOSBVL =GPPushR0Lp * Push string to stack.
ENDCODE
;
-------------------------------------------------------------------------------
Jonathan Busby - <j...@SNMAPOhouston.rr.com>
Remove the random permutation of "NOSPAM" from my e-mail address
before replying.
Thomas Rast
> 1) Use SysRPL / Emulated Saturn assembly to reserve a chunk of memory
> to play with.
>
> 2) Jump to ARM land, and do something that requires a decent amount of
> RAM for working.
>
> 3) Finally, return some of the allocated RAM to the system. The rest
> will be used as an object to be placed on the stack, so I need to tell
> the OS not to override it. This could be done in SysRPL or assembly.
The solution below is a variation on the following theme:
::
ERRSET
CODE
GOTO start
ENDCODE
ERRTRAP
::
GARBAGE
CODE
*start
SAVE GOSBVL MAKERAM$
% ML code goes here...
% if you run out of memory call
GOVLNG GPMEMERR
% ...
GOSBVL Shrink$
GOVLNG GPPushR0Lp % or whatever
ENCODE
;
;
Here 1) is handled by MAKERAM$ and 3) by Shrink$. It tries to do its
job without garbage collecting first, and simply restarts from the
beginning if it runs out of memory. This works very well as long as
the average execution time is short, and the ML code part does not
change the stack. Pivo's ML tutorial file has this and more examples
that show how you can allocate memory for use in ML programs:
http://www.hpcalc.org/details.php?id=5007
It sets up some registers before entering ARM mode, and expects you to
return something too:
* Saturn register contents when entering ARM code:
R0[A]: Start address of your memory zone, pointing at prologue
R1[A]: Address of the object on stack level 1
D[A]: Number of free nibbles remaining
* Saturn register contents when leaving ARM code:
D0: End address of the object you want to push
CRY: ON if you ran out of memory, the code will call the garbage
collector and then run your ARM code again from the start.
Note that the carry flag is always clear after MOVEDOWN on
the 49G, and since that's deliberate (it returns with
RTNCC) I assume it's the same on the 49G+.
Note that even though the arguments passed in for the ARM code to use
are only A fields (5 nibbles), the code clears the rest of the
registers. So unless I'm missing something, you can simply load the
lower half of the register into an ARM register, which will then be
all zeros in the upper 12 bits and the A field in the lower 20.
Here's what (Saturn) memory looks like when entering ARM mode:
R0 +5 +10 +10+D[A] ??
| | | | |
v v v v v
C2A20sssssxxx..xxxcccc...cccc0..0
* C2A20 is the string object prologue (DOCSTR=#02A2C), which you
likely want to change to 41620 (DOINT=#02614) for a ZINT either from
ARM code or by uncommenting the line near the end
* sssss is the current size of the string object, which as I said you
must leave untouched
* xxx..xxx are D[A] nibbles of scratch space that you can use for
anything you want, and write your result to before returning
* ccc..ccc is the ARM code aligned to a 32-bit boundary
* 0..0 are 0-7 nibbles of padding required to achieve the 32-bit
alignment
Remember that R0 does not necessarily point at a byte boundary.
Here's the source code:
::
CK1NoBlame
DUPTYPEZINT? NcaseTYPEERR
ERRSET
CODE
GOTO start
ENDCODE
ERRTRAP
::
GARBAGE
CODE
*start
GOSBVL SAVPTR
A=0.W A=DAT1.A R1=A.W
D=0.W GOSBVL MAKERAM$
A=0.W A=R0.A R0=A.W
AD0EX A+C.A B=A.A
LC(5) (end)-(begin) RSTK=C B-C.A
LC FFFF8 C&B.A D1=C
C=A-C.A D-C.A
SKNC { *memerr GOVLNG GPMEMERR }
GOSUB end
*begin
% ARM code goes here
*end
C=RSTK B=C.A D0=C
C=RSTK GOSBVL MOVEDOWN
C=B.A INTOFF $80BFF INTON
% If the following line fails ("jump too long") try to substitute the
% next one
GOC memerr
% SKNC { GOVLNG GPMEMERR }
GOSBVL Shrink$
% Uncomment the following line if you want a ZINT as a result
% C=R0.W D0=C LC(5) DOINT DAT0=C.A
GOVLNG GPPushR0Lp
ENDCODE
;
SWAPDROP
;
Note: This is only a template. Do *not* try running it without adding
ARM code that correctly sets up registers before returning, as
explained above. It won't work if you just remove the $80BFF or leave
it unchanged.
I have again only tested this on the 49G, as far as I could. Use at
your own risk and always back up your RAM.
- Thomas
--
If you want to reply by mail, substitute my first and last name for
'foo' and 'bar', respectively.
Werner Huysegoms
Just do
::
NULLHXS #8000 EXPAND % reserve 32k
CODE
GOSBVL =SAVPTR
... code ...
GOSBVL ="D0=DSKTOP"
A=DAT0.A R0=A.W % setup string start
LC 0400A C+A.A D0=C % .. and end
% Shrink$ will need R0.A to point at the string obj in TEMPOB
% D0 to point just past the new end point
% and the string will need to be the last object in TEMPOB
% (EXPAND took care of that)
GOSBVL =Shrink$
GOVLNG =GPPushR0Lp
ENDCODE
;
@
Werner
Al Borowski
The greyscale program has been put on hold since HP support still havn't
given me a replacement calculator :-(
Al
Thomas Rast
would align the ARM code to a word boundary and then execute the
unaligned code. The same warnings as before apply, you *need* a chunk
of ARM code that at least sets D0 to a sensible value. However, this
one has been tested on an actual 49G+, so it should work.
Changes are indicated by %% comments:
::
CK1NoBlame
DUPTYPEZINT? NcaseTYPEERR
ERRSET
CODE
GOTO start
ENDCODE
ERRTRAP
::
GARBAGE
CODE
*start
GOSBVL SAVPTR
A=0.W A=DAT1.A R1=A.W
D=0.W GOSBVL MAKERAM$
A=0.W A=R0.A R0=A.W
AD0EX A+C.A B=A.A
LC(5) (end)-(begin) RSTK=C B-C.A
LC FFFF8 C&B.A B=C.A D1=C %% added B=C.A here
C=A-C.A D-C.A
SKNC { *memerr GOVLNG GPMEMERR }
GOSUB end
*begin
% ARM code goes here
*end
C=RSTK D0=C %% removed B=C.A here
C=RSTK GOSBVL MOVEDOWN
C=B.A INTOFF $80BFF INTON
% If the following line fails ("jump too long") try to substitute the
% next one
GOC memerr
% SKNC { GOVLNG GPMEMERR }
GOSBVL Shrink$
% Uncomment the following line if you want a ZINT as a result
% C=R0.W D0=C LC(5) DOINT DAT0=C.A
GOVLNG GPPushR0Lp
ENDCODE
;
SWAPDROP
;
--
Jonathan Busby
Note that you don't need to drop back to RPL in order to perform a
garbage collection. See this code snippet for example :
CODE
start
GOSBVL =SAVPTR
.
.
.
* Prepare to perform GC.
A=PC
- LC(5) (-)-(start)+10
A=A-C A
R4=A
D0=(5) =OSAVE
DAT0=A A
D0=(4) =IRAMBUFF
LCHEX 1700734A10613EF8
DAT0=C W
D0=D0+ 16
LCHEX 3B182C2412E41
DAT0=C 13
GOSBVL =IRAMBUFF * Perform GC.
* Resume execution of code object.
.
.
.
* The above LCHEX constants are the hex representation of the
* following code:
*
* GOSBVL =GARBAGECOL
* D0=(4) =OSAVE
* C=RSTK
* A=R4
* C=C-A A
* A=DAT0 A
* C=C+A A
* PC=C
ENDCODE
Anyway, getting back to the main topic of the thread, I think that a
better way of solving the ARM code alignment problem was suggested
here :
http://groups.google.com/groups?selm=cnee309seo56uqm48c7a97cd8o9lgkvp97%404ax.com
Specifically, in-place movement of the ARM code instead of copying.
This has three major advantages over the copying approach:
(1) Probably the most important, it uses half the memory.
(2) Since there is no copying involved and the ARM code is
moved only when needed, there's no speed penalty.
(3) Easier to interface with Saturn assembly since the ARM
code doesn't have to be loaded from the stack. It can be
incorporated directly into the code object.
Anyway, here's some example code. Note that from "simulated" runs on
my 48GX it appears to work in principle, but somebody would have to
use a 49G+ to verify this :
CODE
GOSBVL =SAVPTR
.
.
.
GOSUBL +
CON(1) 9
BSS 8
armstart
INCLUDE armhex.h
armend
+
C=RSTK
D0=C
D=C A
A=0 A
A=DAT0 1
A=A+C A
B=A A
A=C A
A=A+CON A, 8
C=A A
LC(1) 8
C=C&A A
A=C A
RSTK=C
C=C-D A
DAT0=C 1
?A=B A
GOYES done
LC(5) (armend)-(armstart)
?B>=A A
GOYES +
A=A+C A
B=B+C A
+ D1=A
A=B A
D0=A
GONC +
BUSCC
CON(1) 6 * MOVEDN
GONC done
+ BUSCC
CON(1) 7 * MOVEUP
done C=RSTK
BUSCC
CON(2) #FF * ARMSAT
.
.
.
ENDCODE
( Note that above I assume that MOVEDN and MOVEUP have the same
entry/exit conditions as their Saturn counterparts. )
"armhex.h" is the hex dump of the raw ARM machine code in HPTOOLS
NIBHEX format generated using eg. something like this :
http://groups.google.com/groups?selm=v2si40l1lrolp6ku1u8361jkc42hc39462%404ax.com
While the above code is self modifying, it's only slightly more
complicated in the case of port 0 library routines. There'd be no need
to recompute the library's checksum since the ARM code can only be in
8 possible relative positions. You'd just need a small precomputed
table of 8 CRCs corresponding to each position.
Jonathan Busby
<j...@SNMAPOhouston.rr.com> wrote:
> (3) Easier to interface with Saturn assembly since the ARM
> code doesn't have to be loaded from the stack.
Er, once again, really do try to not post when you're *just* about to
go to bed. ;) I think I'm a little confused. That should be "since the
ARM code doesn't have to be executed from a separate region of memory
whose relative position is possibly non-fixed." ;)
Thomas Rast
> Specifically, in-place movement of the ARM code instead of copying.
Keep in mind that if you do this inside a library that is stored in
port 0, the library will be invalid afterwards...
- Thomas
Jonathan Busby
wrote:
>Jonathan Busby <j...@SNMAPOhouston.rr.com> writes:
>
>> Specifically, in-place movement of the ARM code instead of copying.
>
>Keep in mind that if you do this inside a library that is stored in
>port 0, the library will be invalid afterwards...
>
>- Thomas
Quoted from my post :
Jean-Yves Avenard
> GOSBVL =Shrink$ * Truncate all the string data
> * starting at D0 and resize
> * accordingly. Unused memory is
> * reclaimed by the OS.
>
You could also use the new ASM calls from the MetaKernel:
Shrink$Any.
Shrink$ only works if the strings is the last object in TEMPOB which is
not always the case
Shrink$Any will work on every HP-String-like no matter where they are in
TEMPOB
Jean-Yves
Jean-Yves Avenard
> Sorry that I'm again replying to myself, but there's a bug in this: It
> would align the ARM code to a word boundary and then execute the
> unaligned code. The same warnings as before apply, you *need* a chunk
> of ARM code that at least sets D0 to a sensible value. However, this
> one has been tested on an actual 49G+, so it should work.
>
Something that you would like to know about the ARM code...
There are nearly 128KB of RAM available for the ARM on the 49G+ (that's
why the port1 is only 128KB now).
Jean-Yves
Jean-Yves Avenard
[intersting article snipped]
There is still a major problem related to allocating/freeing memory.
The code could shift after a garbage collector and thus the programmer
should be very careful at how to handle pointers to an object.
Jean-Yves
Jonathan Busby
<j...@SNMAPOhouston.rr.com> wrote:
> BUSCC
> CON(1) 6 * MOVEDN
> GONC done
>
>+ BUSCC
> CON(1) 7 * MOVEUP
>
>
>done C=RSTK
> BUSCC
> CON(2) #FF * ARMSAT
Another slight correction : All these CON pseudo-ops should have "2"
as their parameter.
Thomas Rast
> Quoted from my post :
>
> "While the above code is self modifying, it's only slightly more
> complicated in the case of port 0 library routines. There'd be no need
> to recompute the library's checksum since the ARM code can only be in
> 8 possible relative positions. You'd just need a small precomputed
> table of 8 CRCs corresponding to each position."
I apologize for not reading your entire post, but I don't think 8 will
be enough. Suppose your ARM code consists of the nibbles 01234567,
and it has to be executed from the start of the area this time. Then
your scratch area looks like
01234567xxxxxxx
The contents of xxxxxxx depend on which positions the code was
executed from on previous runs. E.g. the following are all possible:
012345671234567
........5674567
........7777777
If I did the maths right, there are 2^6 possibilities: Going backwards
from the second to last nibble, you may or may not have executed it at
each of the six positions.
Since ARM code seems to be quite big compared to Saturn ML, it might
be a good idea to use a self-decompressing launcher. (Too lazy to
write one now, sorry.)
Jonathan Busby
wrote:
>Jonathan Busby <j...@SNMAPOhouston.rr.com> writes:
>
>> Quoted from my post :
>>
>> "While the above code is self modifying, it's only slightly more
>> complicated in the case of port 0 library routines. There'd be no need
>> to recompute the library's checksum since the ARM code can only be in
>> 8 possible relative positions. You'd just need a small precomputed
>> table of 8 CRCs corresponding to each position."
>
>I apologize for not reading your entire post, but I don't think 8 will
>be enough. Suppose your ARM code consists of the nibbles 01234567,
>and it has to be executed from the start of the area this time. Then
>your scratch area looks like
>
> 01234567xxxxxxx
>
>The contents of xxxxxxx depend on which positions the code was
>executed from on previous runs. E.g. the following are all possible:
>
> 012345671234567
> ........5674567
> ........7777777
>
>If I did the maths right, there are 2^6 possibilities: Going backwards
>from the second to last nibble, you may or may not have executed it at
>each of the six positions.
Of course, I left out some details , namely the assumption that the
unused nibbles would be zeroed out upon a move. These would be divided
into two blocks padding the beginning and the end of the ARM code. The
zeroing operation would entail two Saturn memory writes at the most
which is negligible performance and size wise.
Camille
Jonathan Busby <j...@SNMAPOhouston.rr.com> wrote:
> While the above code is self modifying, it's only slightly more
> complicated in the case of port 0 library routines. There'd be no need
> to recompute the library's checksum since the ARM code can only be in
> 8 possible relative positions. You'd just need a small precomputed
> table of 8 CRCs corresponding to each position.
I missed something (I don't know much about CRC):
- do you store your CRC table in your library ?
- in this case, how do you solve the "fixed-point" problem ?
Thanks,
Camille
Veli-Pekka Nousiainen
news:c31hs4$22fbjt$1...@ID-177907.news.uni-berlin.de...
> Thomas Rast wrote:
X
X
> Something that you would like to know about the ARM code...
>
> There are nearly 128KB of RAM available for the ARM on the 49G+ (that's
> why the port1 is only 128KB now).
>
> Jean-Yves
HP should release all this information, it's of no use to anybody else
BUT this community could start new phenomena of "Synthetic" programming
Thank you and Cyrille for hints so far, but we need a permission to you
to releve all the nessessay interface to do 3rd party programs using ARM
There's no need to releave any actual Saturn&ARM system code
just the access method's for doing 3rd party applications
[VPN]
Al Borowski
> There are nearly 128KB of RAM available for the ARM on the 49G+ (that's
> why the port1 is only 128KB now).
>
> Jean-Yves
Hi Jean-Yves...
This would be extremely useful for a program I'm writing. Is there any
chance you could let me know how to use it? (Even if you could just give
me the Saturn or ARM address of it ..) :-)
thanks,
Al
Jonathan Busby
wrote:
>In article <nh4750hrvko2b32ve...@4ax.com>,
> Jonathan Busby <j...@SNMAPOhouston.rr.com> wrote:
>
>> While the above code is self modifying, it's only slightly more
>> complicated in the case of port 0 library routines. There'd be no need
>> to recompute the library's checksum since the ARM code can only be in
>> 8 possible relative positions. You'd just need a small precomputed
>> table of 8 CRCs corresponding to each position.
>
>I missed something (I don't know much about CRC):
>- do you store your CRC table in your library ?
Yes.
>- in this case, how do you solve the "fixed-point" problem ?
What problem? The library is just data (remember we're use the von
Neumann architecture :) . All of this data, including the CRC table,
is static except for the region containing the ARM code. That area
consists of a variable 1-nibble offset which records where in the
region the ARM code starts relative to the offset, and of course it
also consists of the ARM code plus 8 nibbles of padding both of which
follow the offset. The padding is always 8 zero nibbles and is broken
up into two contiguous chunks (either of which may have a size of zero
) which precede and follow the ARM code respectively. So, if "ofs"
represents the offset, which is constrained to the range 1-9, then the
format of the whole region graphically is :
(view with fixed width font)
Number of nibbles: 1 ofs-1 varies* 9-ofs
[ofs] [pre-padding] [ARM code] [post-padding]
* But predetermined at compile time and static afterwards.
As you can see, there are 8 possible states for the data to be in,
corresponding to each offset value, and therefore there are eight
possible CRC values corresponding to each of these states. Quite
simple. Don't know what the confusion is about.
>Thanks,
You're welcome. :) Hope this helps...
>
>Camille
Jonathan Busby
Man I love my luck. Cable connection went down just after I posted my
previous message, before I could reply to myself. It's a conspiracy I
tell you. ;) (btw. While Road Runner has 400KByte/s downstream
bandwidth, their service quality is crap. There are service
interruptions at least once a week, and if you're lucky, you'll get
one just at the right time that lasts for hours or more - like this
one. :)
On Mon, 15 Mar 2004 08:16:39 -0600, Jonathan Busby
<j...@SNMAPOhouston.rr.com> wrote:
>As you can see, there are 8 possible states for the data to be in,
A slight clarification : The reason there are 8 possible states
instead of 9 is that an offset value of 1 can never occur, so my
statement about it being in the range 1-9 was a little inaccurate.
Also, this means that the pre-padding region will contain at least 1
nibble, and therefore my claim about the possibility of that region
having a size of zero was also wrong. So actually, you only need 7
nibbles of padding, but if you're really that obsessed with space
savings then I don't think you'd be using ARM in the first place. ;)
Camille
Jonathan Busby <j...@SNMAPOhouston.rr.com> wrote:
> >- in this case, how do you solve the "fixed-point" problem ?
>
> What problem? The library is just data (remember we're use the von
> Neumann architecture :) .
Ok, lambda-mode OFF.
> All of this data, including the CRC table,
> is static except for the region containing the ARM code.
> [...]
> As you can see, there are 8 possible states for the data to be in,
> corresponding to each offset value, and therefore there are eight
> possible CRC values corresponding to each of these states. Quite
> simple. Don't know what the confusion is about.
My question was the following: you have a static part "s" and
a changing part "c". "s" contains a CRC table "x". So your code is
"s x c".
Even if "c" is fixed, you are trying to compute x so that
CRC(s x c) = x.
How do you solve this kind of equation ?
Camille
Jonathan Busby
wrote:
>My question was the following: you have a static part "s" and
>a changing part "c". "s" contains a CRC table "x". So your code is
>"s x c".
>Even if "c" is fixed, you are trying to compute x so that
>CRC(s x c) = x.
>How do you solve this kind of equation ?
>
>Camille
Er, Uh oh - heh. Looks like you're the only one paying attention
around here. You point out a very important problem, something I
didn't even think of. For a minute there I was really worried I had
done something ultra-braindead, but fortunately (for me ;) the
solution is quite simple. First the CRC table is located at the *end*
of the library, just before the library's CRC. Secondly, and the most
important detail, the CRCs in the table are the possible CRCs of all
the library data *up to but not including* the CRC table itself. To
get the CRC of the whole library, you retrieve the CRC from the table
that corresponds to the current state of all the data preceding the
table, "prime" the CRC generator with this value, and then take the
CRC of the table (which is 16 bytes). Now you have the final CRC of
the entire library.
If you are really speed conscious, then note that by taking advantage
of the properties of polynomial arithmetic mod 2, we can forgo the
above CRC calculation. If P1(x) represents the library data, P2(x) the
CRC table, D(x) the divisor, and a the size in bits of the CRC table,
then the final CRC can be calculated from the library and table CRCs
by using a few XOR and bitwise operations based on the simple fact
that:
[ P1(x)*x^a + P2(x) ] mod D(x) = P1(x)*x^a mod D(x) + P2(x) mod D(x)
The details related to the fact that the CRC dividend polynomial is
always multiplied by x^16 are not hard to work out.
Jonathan Busby
<j...@SNMAPOhouston.rr.com> wrote:
>A slight clarification : The reason there are 8 possible states
>instead of 9 is that an offset value of 1 can never occur
That is, it can never occur if my original code didn't have an
off-by-one error in it. ;) Specifically, the "A=A+CON A, 8" should be
an "A=A+CON A, 9" . But while you're at it, why not just get a 1
nibble savings and change "BSS 8" to "BSS 7", "CON(1) 9" to "CON(1)
8", and leave the "A=A+CON A, 8" instruction unmodified.
Camille
Jonathan Busby <j...@SNMAPOhouston.rr.com> wrote:
> First the CRC table is located at the *end*
> of the library, just before the library's CRC. Secondly, and the most
> important detail, the CRCs in the table are the possible CRCs of all
> the library data *up to but not including* the CRC table itself. To
> get the CRC of the whole library, you retrieve the CRC from the table
> that corresponds to the current state of all the data preceding the
> table, "prime" the CRC generator with this value, and then take the
> CRC of the table (which is 16 bytes). Now you have the final CRC of
> the entire library.
OK
> If you are really speed conscious, then note that by taking advantage
> of the properties of polynomial arithmetic mod 2, we can forgo the
> above CRC calculation. If P1(x) represents the library data, P2(x) the
> CRC table, D(x) the divisor, and a the size in bits of the CRC table,
> then the final CRC can be calculated from the library and table CRCs
> by using a few XOR and bitwise operations based on the simple fact
> that:
>
> [ P1(x)*x^a + P2(x) ] mod D(x) = P1(x)*x^a mod D(x) + P2(x) mod D(x)
>
>
> The details related to the fact that the CRC dividend polynomial is
> always multiplied by x^16 are not hard to work out.
You have shown that you can precompute "P1(x)*x^a mod D(x)", the shifted
CRC (so that you don't have to "initiate" the CRC generator with it for
the table). But again (!), where would you store the CRC of the table?...
(exactly the same problem as before)
It seems to me that there is no way to avoid the CRC computation for the
table.
Camille
Jonathan Busby
wrote:
>> If you are really speed conscious, then note that by taking advantage
>> of the properties of polynomial arithmetic mod 2, we can forgo the
>> above CRC calculation. If P1(x) represents the library data, P2(x) the
>> CRC table, D(x) the divisor, and a the size in bits of the CRC table,
>> then the final CRC can be calculated from the library and table CRCs
>> by using a few XOR and bitwise operations based on the simple fact
>> that:
>>
>> [ P1(x)*x^a + P2(x) ] mod D(x) = P1(x)*x^a mod D(x) + P2(x) mod D(x)
>>
>>
>> The details related to the fact that the CRC dividend polynomial is
>> always multiplied by x^16 are not hard to work out.
>
>You have shown that you can precompute "P1(x)*x^a mod D(x)", the shifted
>CRC (so that you don't have to "initiate" the CRC generator with it for
>the table). But again (!), where would you store the CRC of the table?...
>(exactly the same problem as before)
No, not the same problem. I should have been more specific when I said
"can be calculated" in relation to the final CRC. Yes, the table CRC
will be stored after the table, but I didn't say that this totally
removes any need for a CRC calculation, otherwise we'd have the
original recursion problem you pointed out. The only CRC calculation
needed for the optimized version involves initializing the CRC
generator with the CRC computed using the above mentioned equality,
and then taking the CRC of the 2-byte table CRC, which constitutes the
last 2 bytes of the library (not including the library CRC). This is
"a lot" better than having to do 16 bytes, if you're counting such
tiny performance gains in a relative sense. :)
>It seems to me that there is no way to avoid the CRC computation for the
>table.
As far as I can tell, there is no readily apparent way to avoid a
minimal 2 byte CRC computation, but you can avoid computing the CRC of
the table.
>
>Camille
Camille
Jonathan Busby <j...@SNMAPOhouston.rr.com> wrote:
> No, not the same problem. I should have been more specific when I said
> "can be calculated" in relation to the final CRC. Yes, the table CRC
> will be stored after the table, but I didn't say that this totally
> removes any need for a CRC calculation, otherwise we'd have the
> original recursion problem you pointed out. The only CRC calculation
> needed for the optimized version involves initializing the CRC
> generator with the CRC computed using the above mentioned equality,
> and then taking the CRC of the 2-byte table CRC, which constitutes the
> last 2 bytes of the library (not including the library CRC). This is
> "a lot" better than having to do 16 bytes, if you're counting such
> tiny performance gains in a relative sense. :)
One more point: you can precompute both shifts in the CRC to avoid
initializing the CRC generator, you'll just XOR twice at the end:
- read the CRC x of the lib (except CRC table) in the table (assuming it
has been multiplied by x^18);
- read the CRC y of the CRC table, located after the table (assuming it
has been multiplied by x^2);
- compute the two bytes CRC z of y;
- the result is (x XOR y XOR z).
> >It seems to me that there is no way to avoid the CRC computation for the
> >table.
>
> As far as I can tell, there is no readily apparent way to avoid a
> minimal 2 byte CRC computation, but you can avoid computing the CRC of
> the table.
I agree with you.
Camille
Jonathan Busby
wrote:
>One more point: you can precompute both shifts in the CRC to avoid
>initializing the CRC generator, you'll just XOR twice at the end:
>- read the CRC x of the lib (except CRC table) in the table (assuming it
>has been multiplied by x^18);
>- read the CRC y of the CRC table, located after the table (assuming it
>has been multiplied by x^2);
(By the way, there's a slight error here. The exponents correspond to
bits, not bytes, so multiply them by eight.)
>- compute the two bytes CRC z of y;
>- the result is (x XOR y XOR z).
I'm splitting hairs here, but shouldn't that be "to avoid initializing
the CRC generator with a non-zero value". ;) You always have to
initialize the CRC generator to zero before using it if you want the
CRC to only reflect data read past that point. This consists of
writing 4 zero nibbles to the memory mapped hardware register located
at #104-#107 and can be accomplished in two instructions (not counting
setting a data register to the correct address). So, the method you
pointed out might have a few instruction advantage over the method
with a non-zero initializer, but neither one has any compelling speed
or size advantage over the other.
Anyway, this whole discussion is about avoiding having to take the CRC
of a whole 16 bytes instead of 2, so I think I'd use the above method
if it's smaller, or else it would be inconsistent. ;) (Oh, and I'd be
a hypocrite since I'm a bit freak ;)