title: what is most efficient code to sign-extend large integers?
body: <p>I am writing a code library in x86-64 assembly-language to provide all conventional bitwise, shift, logical, compare, arithmetic and math functions for <code>s0128</code>, <code>s0256</code>, <code>s0512</code>, <code>s1024</code>, <code>s2048</code>, and <code>s4096</code> signed-integer types and <code>f0128</code>, <code>f0256</code>, <code>f0512</code>, <code>f1024</code>, <code>f2048</code>, and <code>f4096</code> floating-point types.</p>
  
  <p>Now I am writing some type conversion routines, and have run into something that should be trivial but takes a lot more instructions than I would expect.  I feel like I must be missing something (some instructions) to make this easier, but so far no luck.</p>
  
  <p>The low 128-bits of the <code>s0256</code> result is simply a copy of the <code>s0128</code> input argument, and all the bits in the upper 128-bits of the <code>s0256</code> result must be set to the most-significant bit in the <code>s0128</code> input argument.</p>
  
  <p>Simple, huh?  But here is the best I can figure so far to convert <code>s0256</code> to <code>s0128</code>.  Ignore the first 4 lines (they're just argument error checks) and last 2 lines (returning from function with no error (rax == 0)).  The 5 lines in the middle are the algorithm in question.  Try to avoid [conditional] jump instructions.</p>
  
  <pre><code>.text
  .align 64
  big_m63:
  .quad  -63, -63                       # two shift counts for vpshaq instruction
  
  big_s0256_eq_s0128:    # (s0256* arg0, const s0128* arg1); # s0256 = s0256(s0128)
    orq        %rdi, %rdi               # is arg0 a valid address ???
    jz         error_argument_invalid   # nope
    orq        %rsi, %rsi               # is arg1 a valid address ???
    jz         error_argument_invalid   # nope
  
    vmovapd    (%rsi), %xmm0            # ymm0 = arg1.ls64 : arg1.ms64 : 0 : 0
    vmovhlps   %xmm0, %xmm0, %xmm1      # ymm1 = arg1.ms64 : arg1.ms64 : 0 : 0
    vpshaq     big_m63, %xmm1, %xmm1    # ymm1 = arg1.sign : arg1.sign : 0 : 0
    vperm2f128 $32, %ymm1, %ymm0, %ymm0 # ymm1 = arg1.ls64 : arg1.ms64 : sign : sign
    vmovapd    %ymm0, (%rdi)            # arg0 = arg1 (sign-extended to 256-bits)
  
    xorq       %rax, %rax               # rax = 0 == no error
    ret                                 # return from function
  </code></pre>
  
  <p>This routine is also non-optimal in that every instruction requires the result of the previous instruction, which prevents parallel execution of any instructions.</p>
  
  <p>Is there a better instruction to right-shift with sign extension?  I cannot find an instruction like <code>vpshaq</code> that accepts an immediate byte to specify shift-count, though I don't know why (many SIMD instructions have immediate 8-bit operands for various purposes).  Also, Intel does not support <code>vpshaq</code>.  Oops!</p>
  
  <p>But look!  StephenCanon has a brilliant solution to this problem below!  Awesome!  That solution has one more instruction than the above, but the <code>vpxor</code> instruction can be put after the first <code>vmovapd</code> instruction and should effectively take no more cycles than the 5 instruction version above.  Bravo!</p>
  
  <p>For completeness and easy comparison, here is the code with the latest StephenCanon enhancement:</p>
  
  <pre><code>.text
  .align 64
  big_s0256_eq_s0128:    # (s0256* arg0, const s0128* arg1); # s0256 = s0256(s0128)
    orq        %rdi, %rdi               # is arg0 a valid address ???
    jz         error_argument_invalid   # nope
    orq        %rsi, %rsi               # is arg1 a valid address ???
    jz         error_argument_invalid   # nope
  
    vmovapd    (%rsi), %xmm0            # ymm0 = arg1.ls64 : arg1.ms64 : 0 : 0
    vpxor      %xmm2, %xmm2, %xmm2      # ymm2 = 0 : 0 : 0 : 0
    vmovhlps   %xmm0, %xmm0, %xmm1      # ymm1 = arg1.ms64 : arg1.ms64 : 0 : 0
    vpcmpgtq   %xmm1, %xmm2, %xmm1      # ymm1 = arg1.sign : arg1.sign : 0 : 0
    vperm2f128 $32, %ymm1, %ymm0, %ymm0 # ymm1 = arg1.ls64 : arg1.ms64 : sign : sign
    vmovapd    %ymm0, (%rdi)            # arg0 = arg1 (sign-extended to 256-bits)
  
    xorq       %rax, %rax               # rax = 0 == no error
    ret                                 # return from function
  </code></pre>
  
  <p>I'm not certain, but not needing to read those two 64-bit shift-counts from memory might also speed the code up slightly.  Nice.</p>