ARM immediate value encoding • Hacker News Board

Re: ARM immediate value encoding

#11

Post by cnvogel » Sun, Jan 12, 2014, 1:44 PM UTC

AshleysBrain wrote: post #5

Very cool and clever scheme. But what happens to immediates that can't be encoded that way?

Here's what you can do to add a "complicated" constant stored elsewhere, in hand-crafted assembler:

    add_something:        ; function starts here (argument r0 == some number)
	ldr r1, __tmp     ; get complicated constant, store in r1
	add r0, r0, r1    ; do the addition r0 = r0 + r1
	bx lr            ; == return result (in r0)
    __tmp:
	.word 0x12345678  ; store complicated constant here

You can play with your compiler, if you call gcc as "gcc -Os -S -o- file.c" if will spit out generated assembler code (-S) on stdout "-o-" for the c-code in file.c.

(but then, gcc prefers to have 4 "compact" adds, instead of loading a constant...)

    $ cat dummy.c
    int
    add_random_number(int a)
    {
            return a + 0x12345678; /* guaranteed to be random */
    }

    $ arm-none-eabi-gcc -S -o- -Os dummy.c
    (...)
    add_random_number:
            @ Function supports interworking.
            @ args = 0, pretend = 0, frame = 0
            @ frame_needed = 0, uses_anonymous_args = 0
            @ link register save eliminated.
            add     r0, r0, #301989888
            add     r0, r0, #3424256
            add     r0, r0, #5696
            add     r0, r0, #56
            bx      lr

Re: ARM immediate value encoding

#12

Post by chris_overseas » Sun, Jan 12, 2014, 1:47 PM UTC

userbinator wrote: post #10

If I've interpreted this correctly, it means that all values between 256 and 65535 can't be encoded this way since they all have the form 0x0000nn00 with a nonzero nn, and those are the bits that can't be gotten to from rotating.

Sure they can, by setting the rotate bits to 0xC (1100). Have a play with the interactive widget near the bottom of the article.

Interestingly, there is some redundancy with this encoding meaning you can't represent a full 2^12 unique values. Eg 0x1 could be represented by 0x1 and 0x0 in the rotate field, 0x4 with 0x1 in the rotate field, 0x10 with 0x2, or 0x40 with 0x3. The same applies for every other combination - this means that there are only (2^12)/4 = 1024 unique values that are representable in total.

Re: ARM immediate value encoding

#13

Post by stephencanon » Sun, Jan 12, 2014, 1:50 PM UTC

userbinator wrote: post #10

If I've interpreted this correctly, it means that all values between 256 and 65535 can't be encoded this way since they all have the form 0x0000nn00 with a nonzero nn, and those are the bits that can't be gotten to from rotating.

Anything of the form 0x0000nn00 is representable, as it has at most eight contiguous non-zero bits starting at an even bit position (i.e. these values are 0x000000nn rotated right by 24). Maybe you're wondering how a rotation of 24 can be encoded in four bits? To get the rotation amount, you double the value of the four-bit field. Only even rotation counts are representable.

Re: ARM immediate value encoding

#14

Post by Symmetry » Sun, Jan 12, 2014, 1:55 PM UTC

stephencanon wrote: post #2

The set of representable ARM immediates is really nice. It's wonderfully useful for writing soft-float and math library routines, where you have very common values with just some high-order bits set: 0x3f800000 // encoding of 1.0f The set of immediate encodings, together with "shifts for free on most operations" (which are closely related features, as the OP points out), went a long way toward preserving my sanity wh…

Do you know a good place for finding out more about the arm64 encoding?

Re: ARM immediate value encoding

#15

Post by stephencanon » Sun, Jan 12, 2014, 1:56 PM UTC

Symmetry wrote: post #14

stephencanon wrote: post #2

The set of representable ARM immediates is really nice. It's wonderfully useful for writing soft-float and math library routines, where you have very common values with just some high-order bits set: 0x3f800000 // encoding of 1.0f The set of immediate encodings, together with "shifts for free on most operations" (which are closely related features, as the OP points out), went a long way toward preserving my sanity wh…

Do you know a good place for finding out more about the arm64 encoding?

ARM's reference manual (http://infocenter.arm.com/help/index.jsp?topic=/com.arm.doc....). You need to create a (free?) account with ARM to download it. Of course, the document has been out for long enough that I'm sure it's available elsewhere for those truly paranoid about creating accounts.

Re: ARM immediate value encoding

#16

Post by userbinator » Sun, Jan 12, 2014, 1:58 PM UTC

stephencanon wrote: post #13

userbinator wrote: post #10

If I've interpreted this correctly, it means that all values between 256 and 65535 can't be encoded this way since they all have the form 0x0000nn00 with a nonzero nn, and those are the bits that can't be gotten to from rotating.

Anything of the form 0x0000nn00 is representable, as it has at most eight contiguous non-zero bits starting at an even bit position (i.e. these values are 0x000000nn rotated right by 24). Maybe you're wondering how a rotation of 24 can be encoded in four bits? To get the rotation amount, you double the value of the four-bit field. Only even rotation counts are representable.

Thanks, overlooked that detail. Very interesting encoding scheme.

Re: ARM immediate value encoding

#17

Post by cnvogel » Sun, Jan 12, 2014, 1:59 PM UTC

stephencanon wrote: post #4

sbanach wrote: post #3

So arm compilers must prefer to, for example, XOR with 0x10000000 rather than AND with 0xEFFFFFFF?

AND with 0xefffffff would become BIC ("bit clear", aka "and not") with 0x10000000. But yes, the basic idea of your comment is correct. Fortunately, compilers are quite good at this sort of thing.

And if you need something like ~(byte

     MVN r0, #0x10000000 ; ro = 0xefffffff

Oh, the joy :-).

Re: ARM immediate value encoding

#18

Post by userbinator » Sun, Jan 12, 2014, 2:01 PM UTC

cnvogel wrote: post #11

AshleysBrain wrote: post #5

Very cool and clever scheme. But what happens to immediates that can't be encoded that way?

Here's what you can do to add a "complicated" constant stored elsewhere, in hand-crafted assembler: add_something: ; function starts here (argument r0 == some number) ldr r1, __tmp ; get complicated constant, store in r1 add r0, r0, r1 ; do the addition r0 = r0 + r1 bx lr ; == return result (in r0) __tmp: .word 0x12345678 ; store complicated constant here You can play with your compiler, if you call gcc as "gcc -Os -…

From my experience on x86, GCC's -Os isn't that great - looks like it's the same for ARM.

Re: ARM immediate value encoding

#19

Post by ColinWright » Sun, Jan 12, 2014, 2:03 PM UTC

Tuna-Fish wrote: post #6

AshleysBrain wrote: post #5

Very cool and clever scheme. But what happens to immediates that can't be encoded that way?

You have to place them in a constant pool and load them.

As others have said, that's not the case. All constants can be constructed by ORing together a small collection of expressible constants. With a little ingenuity "most" require very few instructions to build. FWIW, I have written real-time radar processing embedded software, and rarely had to resort to stored constants.

Re: ARM immediate value encoding

#20

Post by stephencanon » Sun, Jan 12, 2014, 2:07 PM UTC

cnvogel wrote: post #17

stephencanon wrote: post #4

Earlier quoted context omitted.

AND with 0xefffffff would become BIC ("bit clear", aka "and not") with 0x10000000. But yes, the basic idea of your comment is correct. Fortunately, compilers are quite good at this sort of thing.

And if you need something like ~(byte MVN r0, #0x10000000 ; ro = 0xefffffff Oh, the joy :-).

CMN is the real gem. It's an endless source of bugs in the time between when compiler writers discover it and when they figure out how it actually sets flags. ARM would have done well to provide a "here's how you actually use this instruction" guide in the architecture reference manual.