Making Change

I was bored at work this morning so I decided to do a textbook programming exercise: making change. I remember having to do this in CLI C++ in high school but we weren’t allowed to use argv so we had to prompt for inputs. Anyways, here’s the tested and bug-free code I came up with for making change:

/**
 * change - makes change
 */

#ifndef _CHANGE_H
#define _CHANGE_H

struct change
{
	int   dollars;
	short half_dollars;
	short quarters;
	short dimes;
	short nickels;
	short pennies;
};

float make_change(float, float);
struct change *float2change(float);
void  print_change(struct change*);
#endif /* _CHANGE_H */
/**
 * change - makes change
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "change.h"

int main(int argc, char *argv[])
{
	float amt_due, amt_paid, fchange;
	struct change *stch;
	char *c_amt_due, *c_amt_paid, *sentinel;

	if (argc < 3)
	   {
		fprintf(stderr, "change: too few arguments\n");
		exit(-1);
	   }

	/* strip off leading $ if found */
	if (!(c_amt_due = (char*) calloc(sizeof (char), strlen(argv[1]) + 1)))
	   {
	   	perror("calloc");
		exit(-1);
	   }

	if (!(c_amt_paid = (char*) calloc(sizeof (char), strlen(argv[2]) + 1)))
	   {
	   	perror("calloc");
		exit(-1);
	   }

	strcpy(c_amt_due,  argv[1]);
	strcpy(c_amt_paid, argv[2]);

	if (sentinel = strchr(c_amt_due, '$'))
	   {
		/**
		 * We could either roll the pointer forward past the $
		 * or copy the string back one byte.  Either way we burn
		 * a byte of heap.  Rolling forward is easiest.
		 */

		c_amt_due++;
	   }

	if (sentinel = strchr(c_amt_paid, '$'))
		c_amt_paid++;

	/* truncate precision to two decimal places */
	if (sentinel = strchr(c_amt_due, '.')) /* localize as needed */
	   {
		/* cheat by replacing first unwanted character with \0 */
		/* avoid null-pointer bug by checking string length */
		if (strlen(sentinel) > 3)
		   {
			sentinel += 3;
			*sentinel = '\0';
		   }
	   }

	if (sentinel = strchr(c_amt_paid, '.')) /* localize as needed */
	   {
		if (strlen(sentinel) > 3)
		   {
			sentinel += 3;
			*sentinel = '\0';
		   }
	   }

	/* attempt conversion to float */
	amt_due  = (float) strtod(c_amt_due,  NULL);
	amt_paid = (float) strtod(c_amt_paid, NULL);

	/* make change */
	fchange = make_change(amt_due, amt_paid);
	if(!(stch = float2change(fchange)))
	   {
		perror("float2change");
		exit(-1);
	   }
	
	/* print result */
	printf("Result: %.2f\n", fchange);
	print_change(stch);

	/* exit successfully */
	return 0;
}

float
make_change(float due, float paid)
{
	if (due == paid)
		return (0.0f);

	if (due > paid)
	   {
		printf("amount due is greater than amount paid - printing remaining amount\n");
		return (due - paid + 0.001f);
	   }

	return (paid - due + 0.001f);
}

struct change*
float2change(float amt)
{
	static struct change stch;
	int iamt = (int) (amt * 100);

	stch.dollars = iamt / 100;
	iamt -= (stch.dollars * 100);
	stch.half_dollars = iamt / 50;
	iamt -= (stch.half_dollars * 50);
	stch.quarters = iamt / 25;
	iamt -= (stch.quarters * 25);
	stch.dimes = iamt / 10;
	iamt -= (stch.dimes * 10);
	stch.nickels = iamt / 5;
	iamt -= (stch.nickels * 5);
	stch.pennies = iamt;

	return (&stch);
}

void
print_change(struct change *stch)
{
	printf("dollars: %d\nhalf-dollars: %d\nquarters: %d\ndimes: %d\nnickels: %d\npennies: %d\n",
		stch->dollars, stch->half_dollars, stch->quarters, stch->dimes,
		stch->nickels, stch->pennies);
}

And here’s what gcc compiles change.c into with no optimizations on an x64 box with SSE:

	.file	"change.c"
	.section	.rodata
.LC0:
	.string	"change: too few arguments\n"
.LC1:
	.string	"calloc"
.LC2:
	.string	"float2change"
.LC3:
	.string	"Result: %.2f\n"
	.text
.globl main
	.type	main, @function
main:
.LFB5:
	pushq	%rbp
.LCFI0:
	movq	%rsp, %rbp
.LCFI1:
	subq	$112, %rsp
.LCFI2:
	movl	%edi, -52(%rbp)
	movq	%rsi, -64(%rbp)
	cmpl	$2, -52(%rbp)
	jg	.L2
	movq	stderr(%rip), %rcx
	movl	$26, %edx
	movl	$1, %esi
	movl	$.LC0, %edi
	call	fwrite
	movl	$-1, %edi
	call	exit
.L2:
	movq	-64(%rbp), %rax
	addq	$8, %rax
	movq	(%rax), %rax
	movq	$-1, %rcx
	movq	%rax, -72(%rbp)
	movl	$0, %eax
	cld
	movq	-72(%rbp), %rdi
	repnz
	scasb
	movq	%rcx, %rax
	notq	%rax
	subq	$1, %rax
	leaq	1(%rax), %rsi
	movl	$1, %edi
	call	calloc
	movq	%rax, -24(%rbp)
	cmpq	$0, -24(%rbp)
	jne	.L4
	movl	$.LC1, %edi
	call	perror
	movl	$-1, %edi
	call	exit
.L4:
	movq	-64(%rbp), %rax
	addq	$16, %rax
	movq	(%rax), %rax
	movq	$-1, %rcx
	movq	%rax, -80(%rbp)
	movl	$0, %eax
	cld
	movq	-80(%rbp), %rdi
	repnz
	scasb
	movq	%rcx, %rax
	notq	%rax
	subq	$1, %rax
	leaq	1(%rax), %rsi
	movl	$1, %edi
	call	calloc
	movq	%rax, -16(%rbp)
	cmpq	$0, -16(%rbp)
	jne	.L6
	movl	$.LC1, %edi
	call	perror
	movl	$-1, %edi
	call	exit
.L6:
	movq	-64(%rbp), %rax
	addq	$8, %rax
	movq	(%rax), %rsi
	movq	-24(%rbp), %rdi
	call	strcpy
	movq	-64(%rbp), %rax
	addq	$16, %rax
	movq	(%rax), %rsi
	movq	-16(%rbp), %rdi
	call	strcpy
	movq	-24(%rbp), %rdi
	movl	$36, %esi
	call	strchr
	movq	%rax, -8(%rbp)
	cmpq	$0, -8(%rbp)
	je	.L8
	addq	$1, -24(%rbp)
.L8:
	movq	-16(%rbp), %rdi
	movl	$36, %esi
	call	strchr
	movq	%rax, -8(%rbp)
	cmpq	$0, -8(%rbp)
	je	.L10
	addq	$1, -16(%rbp)
.L10:
	movq	-24(%rbp), %rdi
	movl	$46, %esi
	call	strchr
	movq	%rax, -8(%rbp)
	cmpq	$0, -8(%rbp)
	je	.L12
	movq	-8(%rbp), %rax
	movq	$-1, %rcx
	movq	%rax, -88(%rbp)
	movl	$0, %eax
	cld
	movq	-88(%rbp), %rdi
	repnz
	scasb
	movq	%rcx, %rax
	notq	%rax
	subq	$1, %rax
	cmpq	$3, %rax
	jbe	.L12
	addq	$3, -8(%rbp)
	movq	-8(%rbp), %rax
	movb	$0, (%rax)
.L12:
	movq	-16(%rbp), %rdi
	movl	$46, %esi
	call	strchr
	movq	%rax, -8(%rbp)
	cmpq	$0, -8(%rbp)
	je	.L15
	movq	-8(%rbp), %rax
	movq	$-1, %rcx
	movq	%rax, -96(%rbp)
	movl	$0, %eax
	cld
	movq	-96(%rbp), %rdi
	repnz
	scasb
	movq	%rcx, %rax
	notq	%rax
	subq	$1, %rax
	cmpq	$3, %rax
	jbe	.L15
	addq	$3, -8(%rbp)
	movq	-8(%rbp), %rax
	movb	$0, (%rax)
.L15:
	movq	-24(%rbp), %rdi
	movl	$0, %esi
	call	strtod
	cvtsd2ss	%xmm0, %xmm0
	movss	%xmm0, -44(%rbp)
	movq	-16(%rbp), %rdi
	movl	$0, %esi
	call	strtod
	cvtsd2ss	%xmm0, %xmm0
	movss	%xmm0, -40(%rbp)
	movl	-40(%rbp), %eax
	movl	-44(%rbp), %edx
	movl	%eax, -100(%rbp)
	movss	-100(%rbp), %xmm1
	movl	%edx, -100(%rbp)
	movss	-100(%rbp), %xmm0
	call	make_change
	movss	%xmm0, -100(%rbp)
	movl	-100(%rbp), %eax
	movl	%eax, -36(%rbp)
	movl	-36(%rbp), %eax
	movl	%eax, -100(%rbp)
	movss	-100(%rbp), %xmm0
	call	float2change
	movq	%rax, -32(%rbp)
	cmpq	$0, -32(%rbp)
	jne	.L18
	movl	$.LC2, %edi
	call	perror
	movl	$-1, %edi
	call	exit
.L18:
	cvtss2sd	-36(%rbp), %xmm0
	movl	$.LC3, %edi
	movl	$1, %eax
	call	printf
	movq	-32(%rbp), %rdi
	call	print_change
	movl	$0, %eax
	leave
	ret
.LFE5:
	.size	main, .-main
	.section	.rodata
	.align 8
.LC5:
	.string	"amount due is greater than amount paid - printing remaining amount"
	.align 4
.LC6:
	.long	981668463
	.text
.globl make_change
	.type	make_change, @function
make_change:
.LFB6:
	pushq	%rbp
.LCFI3:
	movq	%rsp, %rbp
.LCFI4:
	subq	$32, %rsp
.LCFI5:
	movss	%xmm0, -4(%rbp)
	movss	%xmm1, -8(%rbp)
	movss	-4(%rbp), %xmm0
	ucomiss	-8(%rbp), %xmm0
	jp	.L30
	je	.L24
.L30:
	jmp	.L22
.L24:
	xorps	%xmm0, %xmm0
	movss	%xmm0, -12(%rbp)
	jmp	.L25
.L22:
	movss	-4(%rbp), %xmm0
	ucomiss	-8(%rbp), %xmm0
	ja	.L28
	jmp	.L26
.L28:
	movl	$.LC5, %edi
	call	puts
	movss	-4(%rbp), %xmm0
	movaps	%xmm0, %xmm1
	subss	-8(%rbp), %xmm1
	movss	.LC6(%rip), %xmm0
	movaps	%xmm1, %xmm2
	addss	%xmm0, %xmm2
	movss	%xmm2, -12(%rbp)
	jmp	.L25
.L26:
	movss	-8(%rbp), %xmm0
	movaps	%xmm0, %xmm1
	subss	-4(%rbp), %xmm1
	movss	.LC6(%rip), %xmm0
	movaps	%xmm1, %xmm2
	addss	%xmm0, %xmm2
	movss	%xmm2, -12(%rbp)
.L25:
	movl	-12(%rbp), %eax
	movl	%eax, -20(%rbp)
	movss	-20(%rbp), %xmm0
	leave
	ret
.LFE6:
	.size	make_change, .-make_change
	.local	stch.2857
	.comm	stch.2857,16,16
	.section	.rodata
	.align 4
.LC7:
	.long	1120403456
	.text
.globl float2change
	.type	float2change, @function
float2change:
.LFB7:
	pushq	%rbp
.LCFI6:
	movq	%rsp, %rbp
.LCFI7:
	movss	%xmm0, -20(%rbp)
	movss	-20(%rbp), %xmm1
	movss	.LC7(%rip), %xmm0
	mulss	%xmm1, %xmm0
	cvttss2si	%xmm0, %eax
	movl	%eax, -4(%rbp)
	movl	-4(%rbp), %ecx
	movl	$1374389535, -28(%rbp)
	movl	-28(%rbp), %eax
	imull	%ecx
	sarl	$5, %edx
	movl	%ecx, %eax
	sarl	$31, %eax
	movl	%edx, %ecx
	subl	%eax, %ecx
	movl	%ecx, %eax
	movl	%eax, stch.2857(%rip)
	movl	stch.2857(%rip), %eax
	imull	$100, %eax, %eax
	subl	%eax, -4(%rbp)
	movl	-4(%rbp), %ecx
	movl	$1374389535, -28(%rbp)
	movl	-28(%rbp), %eax
	imull	%ecx
	sarl	$4, %edx
	movl	%ecx, %eax
	sarl	$31, %eax
	movl	%edx, %ecx
	subl	%eax, %ecx
	movl	%ecx, %eax
	movw	%ax, stch.2857+4(%rip)
	movzwl	stch.2857+4(%rip), %eax
	cwtl
	imull	$50, %eax, %eax
	subl	%eax, -4(%rbp)
	movl	-4(%rbp), %ecx
	movl	$1374389535, -28(%rbp)
	movl	-28(%rbp), %eax
	imull	%ecx
	sarl	$3, %edx
	movl	%ecx, %eax
	sarl	$31, %eax
	movl	%edx, %ecx
	subl	%eax, %ecx
	movl	%ecx, %eax
	movw	%ax, stch.2857+6(%rip)
	movzwl	stch.2857+6(%rip), %eax
	movswl	%ax,%edx
	movl	%edx, %eax
	sall	$2, %eax
	addl	%edx, %eax
	leal	0(,%rax,4), %edx
	addl	%edx, %eax
	subl	%eax, -4(%rbp)
	movl	-4(%rbp), %ecx
	movl	$1717986919, -28(%rbp)
	movl	-28(%rbp), %eax
	imull	%ecx
	sarl	$2, %edx
	movl	%ecx, %eax
	sarl	$31, %eax
	movl	%edx, %ecx
	subl	%eax, %ecx
	movl	%ecx, %eax
	movw	%ax, stch.2857+8(%rip)
	movzwl	stch.2857+8(%rip), %eax
	movswl	%ax,%edx
	movl	%edx, %eax
	sall	$2, %eax
	addl	%edx, %eax
	addl	%eax, %eax
	subl	%eax, -4(%rbp)
	movl	-4(%rbp), %ecx
	movl	$1717986919, -28(%rbp)
	movl	-28(%rbp), %eax
	imull	%ecx
	sarl	%edx
	movl	%ecx, %eax
	sarl	$31, %eax
	movl	%edx, %ecx
	subl	%eax, %ecx
	movl	%ecx, %eax
	movw	%ax, stch.2857+10(%rip)
	movzwl	stch.2857+10(%rip), %eax
	movswl	%ax,%edx
	movl	%edx, %eax
	sall	$2, %eax
	addl	%edx, %eax
	subl	%eax, -4(%rbp)
	movl	-4(%rbp), %eax
	movw	%ax, stch.2857+12(%rip)
	movl	$stch.2857, %eax
	leave
	ret
.LFE7:
	.size	float2change, .-float2change
	.section	.rodata
	.align 8
.LC8:
	.string	"dollars: %d\nhalf-dollars: %d\nquarters: %d\ndimes: %d\nnickels: %d\npennies: %d\n"
	.text
.globl print_change
	.type	print_change, @function
print_change:
.LFB8:
	pushq	%rbp
.LCFI8:
	movq	%rsp, %rbp
.LCFI9:
	subq	$16, %rsp
.LCFI10:
	movq	%rdi, -8(%rbp)
	movq	-8(%rbp), %rax
	movzwl	12(%rax), %eax
	movswl	%ax,%edi
	movq	-8(%rbp), %rax
	movzwl	10(%rax), %eax
	movswl	%ax,%r8d
	movq	-8(%rbp), %rax
	movzwl	8(%rax), %eax
	movswl	%ax,%r10d
	movq	-8(%rbp), %rax
	movzwl	6(%rax), %eax
	movswl	%ax,%ecx
	movq	-8(%rbp), %rax
	movzwl	4(%rax), %eax
	movswl	%ax,%edx
	movq	-8(%rbp), %rax
	movl	(%rax), %esi
	movl	%edi, (%rsp)
	movl	%r8d, %r9d
	movl	%r10d, %r8d
	movl	$.LC8, %edi
	movl	$0, %eax
	call	printf
	leave
	ret
.LFE8:
	.size	print_change, .-print_change
	.section	.eh_frame,"a",@progbits
.Lframe1:
	.long	.LECIE1-.LSCIE1
.LSCIE1:
	.long	0x0
	.byte	0x1
	.string	"zR"
	.uleb128 0x1
	.sleb128 -8
	.byte	0x10
	.uleb128 0x1
	.byte	0x3
	.byte	0xc
	.uleb128 0x7
	.uleb128 0x8
	.byte	0x90
	.uleb128 0x1
	.align 8
.LECIE1:
.LSFDE1:
	.long	.LEFDE1-.LASFDE1
.LASFDE1:
	.long	.LASFDE1-.Lframe1
	.long	.LFB5
	.long	.LFE5-.LFB5
	.uleb128 0x0
	.byte	0x4
	.long	.LCFI0-.LFB5
	.byte	0xe
	.uleb128 0x10
	.byte	0x86
	.uleb128 0x2
	.byte	0x4
	.long	.LCFI1-.LCFI0
	.byte	0xd
	.uleb128 0x6
	.align 8
.LEFDE1:
.LSFDE3:
	.long	.LEFDE3-.LASFDE3
.LASFDE3:
	.long	.LASFDE3-.Lframe1
	.long	.LFB6
	.long	.LFE6-.LFB6
	.uleb128 0x0
	.byte	0x4
	.long	.LCFI3-.LFB6
	.byte	0xe
	.uleb128 0x10
	.byte	0x86
	.uleb128 0x2
	.byte	0x4
	.long	.LCFI4-.LCFI3
	.byte	0xd
	.uleb128 0x6
	.align 8
.LEFDE3:
.LSFDE5:
	.long	.LEFDE5-.LASFDE5
.LASFDE5:
	.long	.LASFDE5-.Lframe1
	.long	.LFB7
	.long	.LFE7-.LFB7
	.uleb128 0x0
	.byte	0x4
	.long	.LCFI6-.LFB7
	.byte	0xe
	.uleb128 0x10
	.byte	0x86
	.uleb128 0x2
	.byte	0x4
	.long	.LCFI7-.LCFI6
	.byte	0xd
	.uleb128 0x6
	.align 8
.LEFDE5:
.LSFDE7:
	.long	.LEFDE7-.LASFDE7
.LASFDE7:
	.long	.LASFDE7-.Lframe1
	.long	.LFB8
	.long	.LFE8-.LFB8
	.uleb128 0x0
	.byte	0x4
	.long	.LCFI8-.LFB8
	.byte	0xe
	.uleb128 0x10
	.byte	0x86
	.uleb128 0x2
	.byte	0x4
	.long	.LCFI9-.LCFI8
	.byte	0xd
	.uleb128 0x6
	.align 8
.LEFDE7:
	.ident	"GCC: (GNU) 4.1.2 20080704 (Red Hat 4.1.2-52)"
	.section	.note.GNU-stack,"",@progbits
Advertisements
  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: