.file	"partition.c"
# Lin Jensen recoded the loops of this version
	.text
.globl partition
	.type	partition,@function
partition:
	pushl	%ebp
	movl	%esp, %ebp
	pushl	%ebx
#		     8		12	16		20
#void partition (int a[], int left, int right, int pivotindex,
#     /* OUT */  int* iloc, int* jloc)
#			24	28
	subl	$16, %esp		# space for 4 local vars

	push	%esi		# LJ add, save 2 more regs
	push	%edi
#REGISTER USAGE:
# eax  temporary, current a[]
# ebx  array address
# ecx  limit in inner loops (left or right *4)
# edx  pivot (value)
# esi  i, increment by 4 to use for array indexing
# edi  j,  same for down loop

	movl	20(%ebp), %eax		# eax = pivotindex
	sal	$2,%eax			#  mult by 4
	movl	8(%ebp), %ebx		#  ebx =address of array
	movl	(%ebx,%eax), %edx	#  edx = pivot (value)
	movl	%eax, -8(%ebp)
	movl	12(%ebp), %esi		# i = left
	sal	$2,%esi
	movl	%esi, 12(%ebp)
	movl	16(%ebp), %edi		# j = right
	sal	$2,%edi
	movl	%edi, 16(%ebp)		# i,j,left,right now mult by 4
while1:
	mov	16(%ebp),%ecx		# ecx = right, limit for loop
up:					# for (;i < right; i++)
	cmpl	%ecx, %esi
	jge	down			# end for-up
	movl	(%ebx,%esi), %eax	#     a[i]
	cmpl	%edx, %eax          # if (a[i] > pivot)
	jg	down
.L7:
	addl	$4,%esi
	jmp	up
down:			# down
	mov	12(%ebp),%ecx		# ecx = left, limit for loop
.L10:
	cmpl	%ecx, %edi		# for ( j > left)
	movl	(%ebx,%edi), %eax	#     a[j]  ALWAYS when change reached
	jle	change
.L13:
	cmpl	%edx, %eax		# if (a[j] < pivot) break
	jl	change
.L12:
	sub	$4,%edi			# j--
	jmp	.L10
change:
.L11:					# if (i >= j)
	cmpl	%edi, %esi
	jge	.L3			# break out of while loop
.L15:
# now we have found 2 elements out of place, exchange them
# recall from down-loop,  that 
#	eax = a[j] swap with a[i], 

	xchg	(%ebx,%esi), %eax	
	mov	%eax, (%ebx,%edi)  #put other value in a[j]

# voila, c'est fait, 2 instructions instead of 18
	addl	$4,%esi			# i++
	sub	$4,%edi			# j--
	jmp	while1			# end while(1) loop

# having optimized the loop, we have to validate the code for 
# final exchanges, or write our own. The local variables haven't been maintained
# the easiest thing would be to store them back

.L3:
	sar	$2,%esi
	sar	$2,%edi		# back from offsets to indexes
	mov	%esi,-12(%ebp)	# i
	mov	%edi,-16(%ebp)	# j
	mov	%edx, -8(%ebp)  # pivot

	movl	20(%ebp), %eax		# final exchanges of pivot
	cmpl	-16(%ebp), %eax
	jge	.L16
	movl	20(%ebp), %eax
	leal	0(,%eax,4), %ebx
	movl	8(%ebp), %ecx
	movl	-16(%ebp), %eax
	leal	0(,%eax,4), %edx
	movl	8(%ebp), %eax
	movl	(%eax,%edx), %eax
	movl	%eax, (%ecx,%ebx)
	movl	-16(%ebp), %eax
	leal	0(,%eax,4), %ecx
	movl	8(%ebp), %edx
	movl	-8(%ebp), %eax
	movl	%eax, (%edx,%ecx)
	leal	-16(%ebp), %eax
	decl	(%eax)
.L16:
	movl	20(%ebp), %eax
	cmpl	-12(%ebp), %eax
	jle	.L17
	movl	20(%ebp), %eax
	leal	0(,%eax,4), %ebx
	movl	8(%ebp), %ecx
	movl	-12(%ebp), %eax
	leal	0(,%eax,4), %edx
	movl	8(%ebp), %eax
	movl	(%eax,%edx), %eax
	movl	%eax, (%ecx,%ebx)
	movl	-12(%ebp), %eax
	leal	0(,%eax,4), %ecx
	movl	8(%ebp), %edx
	movl	-8(%ebp), %eax
	movl	%eax, (%edx,%ecx)
	leal	-12(%ebp), %eax
	incl	(%eax)
.L17:
# return OUT args for part. range
	movl	24(%ebp), %edx	#    *iloc = i;     
	movl	-12(%ebp), %eax
	movl	%eax, (%edx)
	movl	28(%ebp), %edx	#    *jloc = j;
	movl	-16(%ebp), %eax
	movl	%eax, (%edx)
	
	pop	%edi
	pop	%esi		# restore additional regs.

	addl	$16, %esp	# release space for local vars.
	popl	%ebx
	leave			#  restore ebp, presumably
	ret
.Lfe1:
	.size	partition,.Lfe1-partition
	.ident	"GCC: (GNU) 3.2.2 20030222 (Red Hat Linux 3.2.2-5)"