/*
 * Copyright (c) 2012-2014 ARM Ltd
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the company may not be used to endorse or promote
 *    products derived from this software without specific prior written
 *    permission.
 *
 * THIS SOFTWARE IS PROVIDED BY ARM LTD ``AS IS'' AND ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL ARM LTD BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

	/* Basic ARM implementation.  This should run on anything except
	   for ARMv6-M, but there are better implementations for later
	   revisions of the architecture.  This version can support ARMv4T
	   ARM/Thumb interworking.  */
/* Parameters and result.  */
#define src1		r0
#define src2		r1
#define result		r0	/* Overlaps src1.  */

/* Internal variables.  */
#define data1		r2
#define data2		r3
#define magic1		r4
#define tmp2		r5
#define tmp1		r12
#define syndrome	r12	/* Overlaps tmp1 */

/* For armv4t and newer, toolchains will transparently convert
   'bx lr' to 'mov pc, lr' if needed. GCC has deprecated support
   for anything older than armv4t, but this should handle that
   corner case in case anyone needs it anyway */
.macro  RETURN
#if __ARM_ARCH <= 4 && __ARM_ARCH_ISA_THUMB == 0
	mov	pc, lr
#else
	bx	lr
#endif
.endm

	.arm
def_fn strcmp
	.cfi_sections .debug_frame
	.cfi_startproc
	eor	tmp1, src1, src2
	tst	tmp1, #3
	/* Strings not at same byte offset from a word boundary.  */
	bne	.Lstrcmp_unaligned
	ands	tmp1, src1, #3
	bic	src1, src1, #3
	bic	src2, src2, #3
	ldr	data1, [src1], #4
	ldreq	data2, [src2], #4
	beq	1f
	/* Although s1 and s2 have identical initial alignment, they are
	   not currently word aligned.	Rather than comparing bytes,
	   make sure that any bytes fetched from before the addressed
	   bytes are forced to 0xff.  Then they will always compare
	   equal.  */
	eor	tmp1, tmp1, #3
	mvn	data2, #MSB
	lsl	tmp1, tmp1, #3
	S2LO	tmp1, data2, tmp1
	ldr	data2, [src2], #4
	orr	data1, data1, tmp1
	orr	data2, data2, tmp1
1:
	/* Load the 'magic' constant 0x01010101.	*/
	str	r4, [sp, #-4]!
	.cfi_def_cfa_offset 4
	.cfi_offset 4, -4
	mov	magic1, #1
	orr	magic1, magic1, magic1, lsl #8
	orr	magic1, magic1, magic1, lsl #16
	.p2align	2
4:
	sub	syndrome, data1, magic1
	cmp	data1, data2
	/* check for any zero bytes in first word */
	biceq	syndrome, syndrome, data1
	tsteq	syndrome, magic1, lsl #7
	ldreq	data1, [src1], #4
	ldreq	data2, [src2], #4
	beq	4b
2:
	/* There's a zero or a different byte in the word */
	S2HI	result, data1, #24
	S2LO	data1, data1, #8
	cmp	result, #1
	cmpcs	result, data2, S2HI #24
	S2LOEQ	data2, data2, #8
	beq	2b
	/* On a big-endian machine, RESULT contains the desired byte in bits
	   0-7; on a little-endian machine they are in bits 24-31.  In
	   both cases the other bits in RESULT are all zero.  For DATA2 the
	   interesting byte is at the other end of the word, but the
	   other bits are not necessarily zero.	 We need a signed result
	   representing the differnece in the unsigned bytes, so for the
	   little-endian case we can't just shift the interesting bits
	   up.	*/
#ifdef __ARM_BIG_ENDIAN
	sub	result, result, data2, lsr #24
#else
	and	data2, data2, #255
	rsb	result, data2, result, lsr #24
#endif
	ldr	r4, [sp], #4
	.cfi_restore 4
	.cfi_def_cfa_offset 0
	RETURN


#if 0
	/* The assembly code below is based on the following alogrithm.	 */
#ifdef __ARM_BIG_ENDIAN
#define RSHIFT <<
#define LSHIFT >>
#else
#define RSHIFT >>
#define LSHIFT <<
#endif

#define body(shift)							\
  mask = 0xffffffffU RSHIFT shift;					\
  data1 = *src1++;							\
  data2 = *src2++;							\
  do									\
    {									\
      tmp2 = data1 & mask;						\
      if (__builtin_expect(tmp2 != data2 RSHIFT shift, 0))		\
	{								\
	  data2 RSHIFT= shift;						\
	  break;							\
	}								\
      if (__builtin_expect(((data1 - b1) & ~data1) & (b1 << 7), 0))	\
	{								\
	  /* See comment in assembler below re syndrome on big-endian */\
	  if ((((data1 - b1) & ~data1) & (b1 << 7)) & mask)		\
	    data2 RSHIFT= shift;					\
	  else								\
	    {								\
	      data2 = *src2;						\
	      tmp2 = data1 RSHIFT (32 - shift);				\
	      data2 = (data2 LSHIFT (32 - shift)) RSHIFT (32 - shift);	\
	    }								\
	  break;							\
	}								\
      data2 = *src2++;							\
      tmp2 ^= data1;							\
      if (__builtin_expect(tmp2 != data2 LSHIFT (32 - shift), 0))	\
	{								\
	  tmp2 = data1 >> (32 - shift);					\
	  data2 = (data2 << (32 - shift)) RSHIFT (32 - shift);		\
	  break;							\
	}								\
      data1 = *src1++;							\
    } while (1)

  const unsigned* src1;
  const unsigned* src2;
  unsigned data1, data2;
  unsigned mask;
  unsigned shift;
  unsigned b1 = 0x01010101;
  char c1, c2;
  unsigned tmp2;

  while (((unsigned) s1) & 3)
    {
      c1 = *s1++;
      c2 = *s2++;
      if (c1 == 0 || c1 != c2)
	return c1 - (int)c2;
    }
  src1 = (unsigned*) (((unsigned)s1) & ~3);
  src2 = (unsigned*) (((unsigned)s2) & ~3);
  tmp2 = ((unsigned) s2) & 3;
  if (tmp2 == 1)
    {
      body(8);
    }
  else if (tmp2 == 2)
    {
      body(16);
    }
  else
    {
      body (24);
    }

  do
    {
#ifdef __ARM_BIG_ENDIAN
      c1 = (char) tmp2 >> 24;
      c2 = (char) data2 >> 24;
#else /* not  __ARM_BIG_ENDIAN */
      c1 = (char) tmp2;
      c2 = (char) data2;
#endif /* not  __ARM_BIG_ENDIAN */
      tmp2 RSHIFT= 8;
      data2 RSHIFT= 8;
    } while (c1 != 0 && c1 == c2);
  return c1 - c2;
#endif /* 0 */


	/* First of all, compare bytes until src1(sp1) is word-aligned. */
.Lstrcmp_unaligned:
	tst	src1, #3
	beq	2f
	ldrb	data1, [src1], #1
	ldrb	data2, [src2], #1
	cmp	data1, #1
	cmpcs	data1, data2
	beq	.Lstrcmp_unaligned
	sub	result, data1, data2
	RETURN

2:
	stmfd	sp!, {r4, r5}
	.cfi_def_cfa_offset 8
	.cfi_offset 4, -8
	.cfi_offset 5, -4
	mov	magic1, #1
	orr	magic1, magic1, magic1, lsl #8
	orr	magic1, magic1, magic1, lsl #16

	ldr	data1, [src1], #4
	and	tmp2, src2, #3
	bic	src2, src2, #3
	ldr	data2, [src2], #4
	cmp	tmp2, #2
	beq	.Loverlap2
	bhi	.Loverlap1

	/* Critical inner Loop: Block with 3 bytes initial overlap */
	.p2align	2
.Loverlap3:
	bic	tmp2, data1, #MSB
	cmp	tmp2, data2, S2LO #8
	sub	syndrome, data1, magic1
	bic	syndrome, syndrome, data1
	bne	4f
	ands	syndrome, syndrome, magic1, lsl #7
	ldreq	data2, [src2], #4
	bne	5f
	eor	tmp2, tmp2, data1
	cmp	tmp2, data2, S2HI #24
	bne	6f
	ldr	data1, [src1], #4
	b	.Loverlap3
4:
	S2LO	data2, data2, #8
	b	.Lstrcmp_tail

5:
#ifdef __ARM_BIG_ENDIAN
	/* The syndrome value may contain false ones if the string ends
	with the bytes 0x01 0x00.  */
	tst	data1, #0xff000000
	tstne	data1, #0x00ff0000
	tstne	data1, #0x0000ff00
	beq	.Lstrcmp_done_equal
#else
	bics	syndrome, syndrome, #0xff000000
	bne	.Lstrcmp_done_equal
#endif
	ldrb	data2, [src2]
	S2LO	tmp2, data1, #24
#ifdef __ARM_BIG_ENDIAN
	lsl	data2, data2, #24
#endif
	b	.Lstrcmp_tail

6:
	S2LO	tmp2, data1, #24
	and	data2, data2, #LSB
	b	.Lstrcmp_tail

	/* Critical inner Loop: Block with 2 bytes initial overlap.  */
	.p2align	2
.Loverlap2:
	S2HI	tmp2, data1, #16
	sub	syndrome, data1, magic1
	S2LO	tmp2, tmp2, #16
	bic	syndrome, syndrome, data1
	cmp	tmp2, data2, S2LO #16
	bne	4f
	ands	syndrome, syndrome, magic1, lsl #7
	ldreq	data2, [src2], #4
	bne	5f
	eor	tmp2, tmp2, data1
	cmp	tmp2, data2, S2HI #16
	bne	6f
	ldr	data1, [src1], #4
	b	.Loverlap2

5:
#ifdef __ARM_BIG_ENDIAN
	/* The syndrome value may contain false ones if the string ends
	with the bytes 0x01 0x00 */
	tst	data1, #0xff000000
	tstne	data1, #0x00ff0000
	beq	.Lstrcmp_done_equal
#else
	lsls	syndrome, syndrome, #16
	bne	.Lstrcmp_done_equal
#endif
	ldrh	data2, [src2]
	S2LO	tmp2, data1, #16
#ifdef __ARM_BIG_ENDIAN
	lsl	data2, data2, #16
#endif
	b	.Lstrcmp_tail

6:
	S2HI	data2, data2, #16
	S2LO	tmp2, data1, #16
4:
	S2LO	data2, data2, #16
	b	.Lstrcmp_tail

	/* Critical inner Loop: Block with 1 byte initial overlap.  */
	.p2align	2
.Loverlap1:
	and	tmp2, data1, #LSB
	cmp	tmp2, data2, S2LO #24
	sub	syndrome, data1, magic1
	bic	syndrome, syndrome, data1
	bne	4f
	ands	syndrome, syndrome, magic1, lsl #7
	ldreq	data2, [src2], #4
	bne	5f
	eor	tmp2, tmp2, data1
	cmp	tmp2, data2, S2HI #8
	bne	6f
	ldr	data1, [src1], #4
	b	.Loverlap1
4:
	S2LO	data2, data2, #24
	b	.Lstrcmp_tail
5:
	/* The syndrome value may contain false ones if the string ends
	   with the bytes 0x01 0x00.  */
	tst	data1, #LSB
	beq	.Lstrcmp_done_equal
	ldr	data2, [src2], #4
6:
	S2LO	tmp2, data1, #8
	bic	data2, data2, #MSB
	b	.Lstrcmp_tail
.Lstrcmp_done_equal:
	mov	result, #0
	.cfi_remember_state
	ldmfd	sp!, {r4, r5}
	.cfi_restore 4
	.cfi_restore 5
	.cfi_def_cfa_offset 0
	RETURN

.Lstrcmp_tail:
	.cfi_restore_state
	and	r2, tmp2, #LSB
	and	result, data2, #LSB
	cmp	result, #1
	cmpcs	result, r2
	S2LOEQ	tmp2, tmp2, #8
	S2LOEQ	data2, data2, #8
	beq	.Lstrcmp_tail
	sub	result, r2, result
	ldmfd	sp!, {r4, r5}
	.cfi_restore 4
	.cfi_restore 5
	.cfi_def_cfa_offset 0
	RETURN
	.cfi_endproc
	.size strcmp, . - strcmp