Demo entry 6657298

test

   

Submitted by anonymous on Nov 03, 2017 at 02:39
Language: GAS. Code size: 2.8 kB.

# search(A[n], target)
#   if n <= 0 then return -1
#
#   tmp <- A[n-1]
#   A[n-1] <- target
#
#   i <- 0
#   while A[i] != target do
#     i <- i+1
#
#   A[n-1] <- tmp
#
#   if i < n-1 then return i
#   else if A[n-1] == target then return n-1
#   else return -1
#

# int lsearch_2(int *A, int n, int target):
#   - args:
#     - %rdi: *A: base pointer of the array
#     - %esi: n: array length
#      - %edx: target:
#   - return:
#     - %eax: ret, position of target with the given array, -1 is not found
#    - local vars:
#      - %rax: *lastEleAddr (sometimes as scratch reg.)
#      - %ecx: ii, loop counter (from 1)
#      - %r8d: i, yet another loop counter

#  .file  "lsearch_2.c"
#  .text
#  .p2align 4,,15
  .globl  lsearch_2
#  .type  lsearch_2, @function

lsearch_2:
.init:
#  .cfi_startproc
  testl    %esi, %esi                # if (n == 0)
  jle      .not_found                #   togo .not_found;

  # note: movslq: Move doubleword to quadword with sign-extension.
  movslq  %esi, %rax                # // intermediate step, rax used as scratch
  leaq    -4(%rdi,%rax,4), %rax     # lastEleAddr = A + n - 1;
  movl    (%rax), %r9d              # int tmp = *lastEleAddr; // tmp = A[n-1]
  movl    %edx, (%rax)              # *lastEleAddr = target; // A[n-1] = target

  cmpl    (%rdi), %edx              # if (A[0] == target)
  je      .found_at_0_pos           #   togo .found_at_0_pos

  movl    $1, %ecx                  # int ii = 1;
#  .p2align 4,,10
#  .p2align 3
                                    # int i;
.loop:                              # do {
  movl  %ecx, %r8d                  #   i = ii;
  addq  $1, %rcx                    #   ii++;
  cmpl  %edx, -4(%rdi,%rcx,4)       # } while (target != A[ii-1])
  jne    .loop

.if_branches:
  movl  %r9d, (%rax)                # *lastEleAddr = tmp // A[n-1] = tmp;
  leal  -1(%rsi), %eax              # // intermediate step, rax used as scratch
  cmpl  %r8d, %eax                  # if (n-1 > i)
  jg  .ret_i                        #   goto .ret_i
  cmpl  %edx, %r9d                  # if (tmp != target)
  jne  .not_found                   #   goto .not_found
  rep ret                           # return ret // REP to avoid AMD branch prediction penalty
#  .p2align 4,,10
#  .p2align 3

.ret_i:
  movl  %r8d, %eax                  # ret = i
  ret                               # return ret
#  .p2align 4,,10
#  .p2align 3

.found_at_0_pos:
  xorl  %r8d, %r8d                  # i = 0
  jmp  .if_branches                 # goto .if_branches

.not_found:
  movl  $-1, %eax                   # ret = -1
  ret                               # return ret
#  .cfi_endproc

# .LFE0:
#  .size  lsearch_2, .-lsearch_2
#  .ident  "GCC: (GNU) 7.2.0"
#  .section  .note.GNU-stack,"",@progbits

This snippet took 0.01 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).