2

I need to perform fast Galois field arithmetic in my application. I have a multiplication function written in assembly that has been optimized for my platform, an MSP430 microcontroller. That function computes the product of two large numbers of arbitrary size, but each number must be represented as an array of 16-bit integers. However, in my project, a Galois field element is represented as an array of 16 64-bit integers. How do I convert my array of 16 64-bit integers into a representation needed by my optimized, assembly-based multiplication function (i.e. an array of 64 16-bit integers)? Of course, simply casting the array as a (UInt16 *) does not work.

The MSP430 is a little-endian architecture. Thanks in advance for any suggestions.

Keron
  • 167
  • 8
  • Use bit-shifting and masking. – Eugene Sh. Feb 02 '17 at 20:13
  • 1
    Not clear what you intend. If you ant 64 bit integers anyway, why not leave this to the compiler? – too honest for this site Feb 02 '17 at 20:19
  • 1
    On a little-endian machine you can simply `memcpy()` the contents of the `uint64[]` to the `uint16[]`. – EOF Feb 02 '17 at 20:21
  • Can you show how the memory layout used in your project differs from the memory layout in the target? In your project, are the 64-bit integers "oversized" in the sense that you actually use only 2 of the 8 bytes of each integer, and the other bytes are always 0? Do you have to rearrange the bytes, or is your source machine also little-endian architecture? I suppose that you do not have to reorder the bits within each byte, right? – Stephan Lechner Feb 02 '17 at 20:28
  • Does your multiplication function compute the result in-place, or in a separate space? I presume it takes the number of elements of each input array as an argument? – John Bollinger Feb 02 '17 at 20:55
  • You could use a union – M.M Feb 02 '17 at 20:55
  • 1
    When you say "a Galois field is represented as [...]", do you mean an *element* of a Galois field? – John Bollinger Feb 02 '17 at 21:01
  • 1
    Why *can't* you simply reinterpret the bytes of your array of `uint64_t` as an array of (four times as many) `uint16_t`? If it's a question of element order then you've no choice but to copy the bytes of the arrays to a temporary work space, in the needed order. Otherwise, since you're handing this off to an assembly function anyway, you're already well and truly in the domain of implementation-defined behavior, and you might as well make use of it. – John Bollinger Feb 02 '17 at 21:16
  • @JohnBollinger I am referring to a Galois field element (I have now edited my original post). Also, you are correct I was able to simply reinterpret the bytes of the array of `uint64_t` as an array of `uint16_t` by casting. For some reason, I was thinking the bytes had to be reordered somehow, but after testing I am getting the correct results. This didn't work for me initially because of other unrelated issues (stack overflow to be specific). – Keron Feb 03 '17 at 21:59

2 Answers2

0

I'm not certain if this is what you want and this solution is incomplete in the sense that it just serves as an example. Additionally it is highly platform dependable. It works on my machine (little_endian). I'm using Code:Blocks under windows.

   typedef struct {
             uint16_t lo_word0;
             uint16_t hi_word0;
             uint16_t lo_word1;
             uint16_t hi_word1;
              }struct_t;



    int main()
    {
       uint64_t buff_64[4]={0xaaaabbbbccccdddd,0xbbbbccccddddeeee,0x1111222233334444,0x8888aaaabbbbcccc};
       uint16_t buff_16[16];
      /*Please note that you may use simply:
        memcpy(buff_16,buff_64,32); 
        however that would result in reverse order
        with respect to the code below */

       struct_t *ptr = (struct_t *)buff_64;

       for(int j=0; j<16; ptr++)
       {
         buff_16[(j++)%16]=ptr->hi_word1;
         buff_16[(j++)%16]=ptr->lo_word1;
         buff_16[(j++)%16]=ptr->hi_word0;
         buff_16[(j++)%16]=ptr->lo_word0;

       } 
        // The check
        for(int j=0;j<16;j++)
        printf("%x\n",buff_16[j]);  

        return 0;
      }
Koorosh Hajiani
  • 94
  • 4
0

As mentioned by @JohnBollinger I was able to simply reinterpret the bytes of the array of uint64_t as an array of uint16_t by casting. For some reason, I was thinking the bytes had to be reordered somehow, but after testing I am getting the correct results. This didn't work for me initially because of other unrelated issues.

Keron
  • 167
  • 8