Mercurial > hg > Papers > 2010 > kent-master

changeset 11:d8adf04b9f63

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
organized repository.
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Tue, 16 Feb 2010 14:40:12 +0900
parents 3d9addf62d0b
children 0f9a0ecc6afb
files quicksort_for_ppc/Makefile quicksort_for_ppc/benchmark.sh quicksort_for_ppc/mc/Makefile quicksort_for_ppc/mc/benchmark.sh quicksort_for_ppc/mc/quicksort_cbc.cbc quicksort_for_ppc/mc/quicksort_cbc.h quicksort_for_ppc/mc/quicksort_test.cbc quicksort_for_ppc/mc/quicksort_test.h quicksort_for_ppc/quicksort_c.c quicksort_for_ppc/quicksort_cbc.cbc quicksort_for_ppc/quicksort_cbc.h quicksort_for_ppc/quicksort_cbc2.cbc quicksort_for_ppc/quicksort_cbc2.h quicksort_for_ppc/quicksort_cbc_inter.cbc quicksort_for_ppc/quicksort_test.cbc quicksort_for_ppc/quicksort_test.h
diffstat 16 files changed, 0 insertions(+), 1470 deletions(-) [+]
line wrap: on
line diff
--- a/quicksort_for_ppc/Makefile	Tue Feb 16 14:35:36 2010 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,38 +0,0 @@
-
-CbCC=/usr/local/cbc/bin/cbc-gcc
-
-#CC=gcc
-CC=/usr/local/cbc/bin/cbc-gcc
-
-HEADERMAKER=../../CbC-scripts/make_headers.py2
-
-# fastcall版では-O0,-O2は動作確認、-O3以上はだめ
-CFLAGS=-g -O2 -fomit-frame-pointer
-#CFLAGS=-g -O2
-#CFLAGS=-g -O0
-#CFLAGS=-g -Os # an error occurred.
-
-.SUFFIXES: .cbc .o
-
-all: quicksort_cbc quicksort_c quicksort_cbc2
-
-.cbc.o:
-	$(CbCC) $(CFLAGS) -c -o $@ $<
-.cbc.h:
-	$(HEADERMAKER) $^ > $@
-
-quicksort_cbc.o: quicksort_cbc.h
-quicksort_cbc2.o: quicksort_cbc2.h
-quicksort_test.o: quicksort_test.h
-
-quicksort_cbc: quicksort_cbc.o quicksort_test.o quicksort_cbc_inter.o
-	$(CC) $(CFLAGS) -o $@ $^
-quicksort_cbc2: quicksort_cbc2.o quicksort_test.o
-	$(CC) $(CFLAGS) -o $@ $^
-
-quicksort_c: quicksort_c.o
-	$(CC) $(CFLAGS) -o $@ $^
-
-
-clean: 
-	rm -rf *.o *.s quicksort_c quicksort_cbc quicksort_cbc2 
--- a/quicksort_for_ppc/benchmark.sh	Tue Feb 16 14:35:36 2010 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,44 +0,0 @@
-#!/usr/bin/env zsh
-
-time=/usr/bin/time
-QS=./quicksort_c
-size=10000000
-seed=123456789
-num=10
-
-
-max=0
-min=99999
-count=0
-amount=0
-
-echo "size of array = $size"
-while [[ $count -lt $num ]]; do
-	usertime=$( $time -p $QS -n $size -s $seed 2>&1 >& - |grep '^user'|tr -s " "|cut -f2 -d" ")
-	#usertime=$(printf "%d" $usertime)
-	echo $usertime
-
-	amount=$(($usertime+$amount))
-	if [[ $usertime -lt $min ]]; then
-	    min=$usertime
-	fi
-	if [[ $usertime -gt $max ]]; then
-	    max=$usertime
-	fi
-	#seed=$seed[1,-2]
-	seed=$(($seed+10))
-	count=$(($count+1))
-done
-
-echo "amount time = $amount"
-echo "maxtime = $max"
-echo "mintime = $min"
-
-amount=$(($amount - $max - $min))
-echo "amount time - mintime - maxtime = $amount"
-count=$(($count-2))
-echo "count = $count"
-averagetime=$(($amount/($count)))
-echo "average time = $averagetime"
-
-
--- a/quicksort_for_ppc/mc/Makefile	Tue Feb 16 14:35:36 2010 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,39 +0,0 @@
-
-CbCC=~/WorkSpace/Mercurial/device/mc
-
-#CC=gcc
-CC=gcc
-
-HEADERMAKER=~/WorkSpace/Mercurial/GCC/CbC-scripts/make_headers.py2
-
-CFLAGS=-g -Wall
-
-.SUFFIXES: .cbc .o .s .c
-
-all: quicksort_cbc quicksort_c quicksort_cbc2
-
-quicksort_c.c quicksort_cbc.cbc quicksort_cbc2.cbc quicksort_test.cbc benchmark.sh:
-	ln -s ../$@
-
-.s.o:
-	$(CC) -c -o $@ $<
-.cbc.s:
-	$(CbCC) $<
-.cbc.h:
-	$(HEADERMAKER) $^ > $@
-
-quicksort_cbc.o: quicksort_cbc.h
-quicksort_cbc2.o: quicksort_cbc2.h
-quicksort_test.o: quicksort_test.h
-
-quicksort_cbc: quicksort_cbc.o quicksort_test.o quicksort_cbc_inter.o
-	$(CC) $(CFLAGS) -o $@ $^
-quicksort_cbc2: quicksort_cbc2.o quicksort_test.o
-	$(CC) $(CFLAGS) -o $@ $^
-
-quicksort_c: quicksort_c.o
-	$(CC) $(CFLAGS) -o $@ $^
-
-
-clean: 
-	rm -rf *.o *.s quicksort_c quicksort_cbc quicksort_cbc2 
--- a/quicksort_for_ppc/mc/benchmark.sh	Tue Feb 16 14:35:36 2010 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,44 +0,0 @@
-#!/usr/bin/env zsh
-
-time=/usr/bin/time
-QS=./quicksort_cbc
-size=10000000
-seed=123456789
-num=10
-
-
-max=0
-min=99999
-count=0
-amount=0
-
-echo "size of array = $size"
-while [[ $count -lt $num ]]; do
-	usertime=$( $time -p $QS -n $size -s $seed 2>&1 >& - |grep '^user'|tr -s " "|cut -f2 -d" ")
-	#usertime=$(printf "%d" $usertime)
-	echo $usertime
-
-	amount=$(($usertime+$amount))
-	if [[ $usertime -lt $min ]]; then
-	    min=$usertime
-	fi
-	if [[ $usertime -gt $max ]]; then
-	    max=$usertime
-	fi
-	#seed=$seed[1,-2]
-	seed=$(($seed+10))
-	count=$(($count+1))
-done
-
-echo "amount time = $amount"
-echo "maxtime = $max"
-echo "mintime = $min"
-
-amount=$(($amount - $max - $min))
-echo "amount time - mintime - maxtime = $amount"
-count=$(($count-2))
-echo "count = $count"
-averagetime=$(($amount/($count)))
-echo "average time = $averagetime"
-
-
--- a/quicksort_for_ppc/mc/quicksort_cbc.cbc	Tue Feb 16 14:35:36 2010 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,244 +0,0 @@
-#include<stdio.h>
-#include<stdlib.h>
-#include<assert.h>
-
-typedef void *stack;
-typedef struct {
-	int size;
-	void *interface;
-	__code  (*ret)(void*, stack) ;
-} frame, *framep;
-
-/* quickstart main routine. */
-typedef struct {
-	int *v;
-	int s;
-	int e;
-} QS_IF ;
-typedef __code  (*RET)(void*);
-
-#include"quicksort_cbc.h"
-
-/* for check. */
-void *mustbefreed;
-
-__code  returner(stack sp)
-{
-	framep fp = (framep)sp;
-	sp += fp->size;
-	goto fp->ret(fp->interface, sp);
-}
-
-__code  quicksort_start(void *arg, stack sp)
-{
-	QS_IF *recvif = arg;
-	int a,b,c,p;
-	a = recvif->v[recvif->s];
-	b = recvif->v[recvif->e];
-	c = recvif->v[(recvif->s+recvif->e)/2];
-
-	//printf("quicksort_start: s=%d,e=%d", recvif->s, recvif->e);
-	if (recvif->e <= recvif->s) goto returner(sp);
-
-	if (a < b) {
-		if (b < c)
-			p = b;
-		else if (a < c)
-			p = c;
-		else 
-			p = a;
-	} else {
-		if (a < c)
-			p = a;
-		else if (b < c)
-			p = c;
-		else 
-			p = b;
-	}
-
-	goto quicksort_divider (recvif, recvif->s, recvif->e, p, sp);
-}
-/* main routine end. */
-
-/* divide routine. */
-__code  quicksort_divider(QS_IF *recvif, int s, int e, int p, stack sp)
-{
-	goto quicksort_divider_s(recvif, s, e, p, sp);
-}
-__code  quicksort_divider_s(QS_IF *recvif, int s, int e, int p, stack sp)
-{
-	if (recvif->v[s]<p) {
-		goto quicksort_divider_s(recvif, s+1, e, p, sp);
-	} else
-		goto quicksort_divider_e(recvif, s, e, p, sp);
-}
-__code  quicksort_divider_e(QS_IF *recvif, int s, int e, int p, stack sp)
-{
-	if (p<recvif->v[e]) {
-		e--;
-		goto quicksort_divider_e(recvif, s, e, p, sp);
-	} else
-		goto quicksort_swapper(recvif, s, e, p, sp);
-}
-__code  quicksort_swapper(QS_IF *recvif, int s, int e, int p, stack sp)
-{
-	if (s<e) {
-		int tmp;
-		tmp = recvif->v[s];
-		recvif->v[s] = recvif->v[e];
-		recvif->v[e] = tmp;
-		goto quicksort_divider(recvif, s+1, e-1, p, sp);
-	} else {
-		goto quicksort_treecall(recvif, s, e, sp);
-	}
-}
-/* divide routin end. */
-
-
-/* recursive call routine. */
-__code  quicksort_treecall(QS_IF *recvif, int s, int e, stack sp)
-{
-	framep fp;
-	QS_IF *outif;
-
-	/* interface for first quicksort_start this segment directly jump to.  */
-	outif = (sp-=sizeof(QS_IF));
-	outif->v = recvif->v;
-	outif->s = recvif->s;
-	outif->e = e;
-	fp = (sp-=sizeof(frame));
-	fp->ret = quicksort_start;
-	fp->interface = recvif;
-	fp->size = sizeof(frame)+sizeof(QS_IF);
-
-	/* recvif is used by second quicksort_start.  */
-	recvif->s = e+1;
-	goto quicksort_start(outif, sp);
-}
-/* recursive call routine end. */
-
-#define STACK_SIZE 10240
-
-typedef struct {
-	__code  (*ret)(void*);
-	void *ret_arg;
-	stack *sp;
-} QS_FINISH;
-__code 
-quicksort(int *v, int s, int e,  RET ret, void *arg )
-{
-	framep fp;
-	stack sp0, sp;
-	sp0 = mustbefreed = malloc(STACK_SIZE);
-	sp = sp0 + STACK_SIZE;
-	QS_FINISH *finish_if;
-	QS_IF *outif;
-	
-	/* interface for quicksort_finish.  */
-	finish_if = (sp -= sizeof(QS_FINISH));
-	finish_if->ret = ret;
-	finish_if->ret_arg = arg;
-	finish_if->sp = sp0;
-
-	/* interface for quicksort_start.  */
-	outif = (sp -= sizeof(QS_IF));
-	outif->v = v;
-	outif->s = s;
-	outif->e = e;
-	/* frame for quicksort_finish.  */
-	fp = (sp -= sizeof(frame));
-	fp->ret = quicksort_finish;
-	fp->interface = finish_if;
-	fp->size = sizeof(frame)+sizeof(QS_IF);
-
-	goto quicksort_start(outif, sp);
-}
-__code 
-quicksort_finish(void *arg, stack sp)
-{
-	QS_FINISH interface;
-	interface = *(QS_FINISH*)arg;
-	//assert((void*)interface.sp==(void*)mustbefreed);
-	free(interface.sp);
-	goto interface.ret(interface.ret_arg);
-}
-
-
-
-#if 0
-void
-quicksort_c(int *v, int s0, int e0, stack sp)
-{
-	int p;
-	int s=s0, e=e0;
-	if (e<=s) return;
-
-	//p = (v[s]+v[(s+e)/2]+v[e])/3;
-	p = mid_point(v[s],v[e],v[(s+e)/2]);
-
-	while (1) {
-		 while (v[s]<p) s++;
-		 while (p<v[e]) e--;
-
-		 if (!(s<e)) break;
-		 SWAP(&v[s], &v[e]);
-		 s++; e--;
-	}
-	assert(e+1==s || s==e);
-
-	quicksort(v, s0, e);
-	quicksort(v, e+1, e0);
-	return;
-}
-
-
-
-/*  --------------------
- *     | args |fp| 
- *  --------------------
- *  +            ↑     -
- *               sp
- */ 
-/* ret segmentへgotoしたときのstack spの状態
- *
- * sp が直接さすのは frame 構造体
- * frame.size:
- * frame.ret: そのret segmentが終了した時にgotoすべきret segment.
- * frame.interface: frame.retへgotoするときのinterface.
- *                  このポインタが指すメモリ領域は stack
- *                  中にあっても良いしなくても良い。
- *                  ただしframe.retを登録した側で解放すべき。
- * sp+sizeof(frame)が指すのは実行中のret segmentのinterface(引数)
- * これは実行中のret segmentがメモリ管理する
- * 通常はこのret segmentが終了する際に sp+=frame.size とすればよい
- */
-__code caller0(void *arg, stack sp)
-{
-	/* interface for caller_finish0.  */
-	double *finish_arg = (sp -= sizeof(double));
-
-	/* arg for quicksort_start.  */
-	outif = (sp -= sizeof(*outif));
-	framep fp = (sp -= sizeof(frame));
-	fp->ret = caller_finish;
-	fp->interface = NULL;
-	fp->size = sizeof(*outif)+sizeof(frame);
-
-	goto quicksort_start(outif, sp);
-}
-__code caller_finish0(void *arg, stack sp)
-{
-}
-
-__code __returner0(void *arg , stack sp)
-{
-	framep fp = sp;
-	sp += fp->size;
-	goto fp->ret(fp->interface, sp);
-}
-
-#endif
-
-
-
-
--- a/quicksort_for_ppc/mc/quicksort_cbc.h	Tue Feb 16 14:35:36 2010 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,26 +0,0 @@
-/* defined in file quicksort_cbc.cbc at offset 354  */
-__code  returner (stack sp);
-
-/* defined in file quicksort_cbc.cbc at offset 462  */
-__code  quicksort_start (void *arg, stack sp);
-
-/* defined in file quicksort_cbc.cbc at offset 1031  */
-__code  quicksort_divider (QS_IF *recvif, int s, int e, int p, stack sp);
-
-/* defined in file quicksort_cbc.cbc at offset 1155  */
-__code  quicksort_divider_s (QS_IF *recvif, int s, int e, int p, stack sp);
-
-/* defined in file quicksort_cbc.cbc at offset 1364  */
-__code  quicksort_divider_e (QS_IF *recvif, int s, int e, int p, stack sp);
-
-/* defined in file quicksort_cbc.cbc at offset 1576  */
-__code  quicksort_swapper (QS_IF *recvif, int s, int e, int p, stack sp);
-
-/* defined in file quicksort_cbc.cbc at offset 1916  */
-__code  quicksort_treecall (QS_IF *recvif, int s, int e, stack sp);
-
-/* defined in file quicksort_cbc.cbc at offset 2547  */
-__code  quicksort (int *v, int s, int e,  RET ret, void *arg );
-
-/* defined in file quicksort_cbc.cbc at offset 3213  */
-__code  quicksort_finish (void *arg, stack sp);
--- a/quicksort_for_ppc/mc/quicksort_test.cbc	Tue Feb 16 14:35:36 2010 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,129 +0,0 @@
-#include<stdio.h>
-#include<stdlib.h>
-#include<assert.h>
-#include<unistd.h>
-
-#include"quicksort_test.h"
-
-#define STACK_SIZE 10240
-
-extern void quicksort_IF();
-
-
-void
-random_initialize(int *v, int size, int min, int max)
-{
-	int i;
-	int diff = max-min+1;
-
-	for (i=0; i<size; i++) {
-		v[i] = min+random()%diff;
-	}
-	return;
-}
-
-static void
-print_array(int *v, int size)
-{
-	int i;
-	printf("[");
-	for (i=0; i<size; i++) {
-		printf("%s%4d", (i%10==0)? "\n  ":" ", v[i]);
-	}
-	printf(" ]\n");
-}
-
-int *IFv;
-int IFs;
-int IFe;
-void* IFret;
-void *IFarg;
-void* IFsp;
-int IFsize;
-
-void
-starter(int size)
-{
-	int *target;
-	void *sp;
-
-	target = (int*)malloc(sizeof(int)*size);
-	if (!target) {
-		perror("malloc");
-		exit(1);
-	}
-
-	random_initialize(target, size, 0, 90);
-
-	sp = malloc(STACK_SIZE);
-	if (!sp) {
-		perror("malloc");
-		exit(1);
-	}
-	//print_array(target, size);
-	//goto quicksort(target, 0, size-1, exit0, (void*)target);
-	IFv=   target;
-	IFs=    0;
-	IFe=    size-1;
-	IFret=  exit0;
-	IFarg=(void*)target;
-	IFsp= sp;
-	IFsize= STACK_SIZE;
-	quicksort_IF();
-
-	printf("bad region\n");
-}
-
-static int size=100;
-
-int
-main(int argc, char **argv)
-{
-	unsigned int seed=0;
-	int opt;
-
-	while ((opt = getopt(argc, argv, "s:n:")) != -1) {
-		switch (opt) {
-			case 's':
-				seed = atoi(optarg);
-				break;
-			case 'n':
-				size = atoi(optarg);
-				break;
-			default:
-				fprintf(stderr, "Usage: %s [-t times] [-n sizeofarray] [-s seed]\n", argv[0]);
-				exit(1);
-		}
-	}
-
-	srandom(seed);
-	starter(size);
-	return 0;
-}
-
-static int
-check_sort(int *v, int size)
-{
-	int i;
-	for (i=0; i<size-1; i++) {
-		if (v[i] > v[i+1])
-			return 0;
-	}
-	return 1;
-}
-
-void
-exit0(void *arg)
-{
-	int b;
-	//print_array(arg, size);
-	b = check_sort(arg, size);
-	if (b) {
-		printf("sorting successful!\n");
-		exit(EXIT_SUCCESS);
-	} else {
-		printf("sorting failure! \n");
-		exit(EXIT_FAILURE);
-	}
-}
-
--- a/quicksort_for_ppc/mc/quicksort_test.h	Tue Feb 16 14:35:36 2010 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,18 +0,0 @@
-/* defined in file quicksort_test.cbc at offset 160  */
-void random_initialize (int *v, int size, int min, int max);
-
-/* defined in file quicksort_test.cbc at offset 322  */
-static void print_array (int *v, int size);
-
-/* defined in file quicksort_test.cbc at offset 564  */
-void starter (int size);
-
-/* defined in file quicksort_test.cbc at offset 1095  */
-int main (int argc, char **argv);
-
-/* defined in file quicksort_test.cbc at offset 1491  */
-static int check_sort (int *v, int size);
-
-/* defined in file quicksort_test.cbc at offset 1620  */
-void exit0 (void *arg);
-
--- a/quicksort_for_ppc/quicksort_c.c	Tue Feb 16 14:35:36 2010 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,183 +0,0 @@
-#include<stdio.h>
-#include<stdlib.h>
-#include<unistd.h>
-#include<assert.h>
-
-static inline void
-SWAP (int *a, int *b)
-{
-	int tmp;
-	tmp = *a;
-	*a = *b;
-	*b = tmp;
-}
-
-static inline int
-mid_point(int a, int b, int c)
-{
-	if (a < b) {
-		if (b < c)
-			return b;
-		else if (a < c)
-			return c;
-		else 
-			return a;
-	} else {
-		if (a < c)
-			return a;
-		else if (b < c)
-			return c;
-		else 
-			return b;
-	}
-}
-
-void
-selectsort(int *v, int s0, int e0)
-{
-	int i,j;
-	int m;
-	int size = e0-s0+1;
-	v += s0;
-	for (i=0; i<size; i++) {
-		m = i;
-		for (j=i+1; j<size; j++) {
-			if (v[m] > v[j])
-				m = j;
-		}
-		if (m!=i)
-			SWAP(&v[i],&v[m]);
-	}
-	return;
-}
-
-void
-quicksort(int *v, int s0, int e0)
-{
-	int p;
-	int s=s0, e=e0;
-#if 0
-	if (e<=s) return;
-	if (e-s<5) {
-		selectsort(v,s0,e0);
-		return;
-	}
-#else
-	if (e<=s) return;
-#endif
-
-	//p = (v[s]+v[(s+e)/2]+v[e])/3;
-	p = mid_point(v[s],v[e],v[(s+e)/2]);
-
-	while (1) {
-		 while (v[s]<p) s++;
-		 while (p<v[e]) e--;
-
-		 if (!(s<e)) break;
-		 SWAP(&v[s], &v[e]);
-		 s++; e--;
-	}
-	assert(e+1==s || s==e);
-
-	quicksort(v, s0, e);
-	quicksort(v, e+1, e0);
-	return;
-}
-
-static void
-print_array(int *v, int size)
-{
-	int i;
-	printf("[");
-	for (i=0; i<size; i++) {
-		printf("%s%4d", (i%10==0)? "\n  ":" ", v[i]);
-	}
-	printf("]\n");
-}
-
-static int
-check_sort(int *v, int size)
-{
-	int i;
-	for (i=0; i<size-1; i++) {
-		if (v[i] > v[i+1])
-			return 0;
-	}
-	return 1;
-}
-
-void
-random_initialize(int *v, int size, int min, int max)
-{
-	int i;
-	int diff = max-min+1;
-
-	for (i=0; i<size; i++) {
-		v[i] = min+random()%diff;
-	}
-	return;
-}
-
-int
-start_sort(int size)
-{
-	int *target;
-
-	target = (int*)malloc(sizeof(int)*size);
-	if (!target) {
-		perror("malloc");
-		exit(1);
-	}
-
-	random_initialize(target, size, 0, 1);
-
-	//print_array(target, size);
-	quicksort(target, 0, size-1);
-	//selectsort(target, 0, size-1);
-	//print_array(target, size);
-	return check_sort(target, size);
-}
-
-int
-main(int argc, char **argv)
-{
-	//unsigned int seed= -1074072728;
-	unsigned int seed;
-	int size=101;
-	int loop=1;
-	int opt, i;
-
-	while ((opt = getopt(argc, argv, "t:s:n:")) != -1) {
-		switch (opt) {
-			case 'n':
-				size = atoi(optarg);
-				break;
-			case 't':
-				loop = atoi(optarg);
-				break;
-			case 's':
-				seed = atoi(optarg);
-				break;
-			default:
-				fprintf(stderr, "Usage: %s [-t times] [-n sizeofarray] [-s seed]\n", argv[0]);
-				exit(1);
-		}
-	}
-
-	printf("start seed = %u\n", seed);
-	printf("sort size = %d\n", size);
-	for (i=0; i<loop; i++) {
-		srandom(seed+i);
-		int b = start_sort(size);
-		if (b) {
-			printf("seed = %d+%u, success\n", i, seed);
-		} else {
-			fprintf(stderr, "sorting failure!  seed=%u+%d\n", seed,i);
-			exit(1);
-		}
-	}
-	exit(0);
-}
-
-
-
--- a/quicksort_for_ppc/quicksort_cbc.cbc	Tue Feb 16 14:35:36 2010 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,244 +0,0 @@
-#include<stdio.h>
-#include<stdlib.h>
-#include<assert.h>
-
-typedef void *stack;
-typedef struct {
-	int size;
-	void *interface;
-	__code  (*ret)(void*, stack) ;
-} frame, *framep;
-
-/* quickstart main routine. */
-typedef struct {
-	int *v;
-	int s;
-	int e;
-} QS_IF ;
-typedef __code  (*RET)(void*);
-
-#include"quicksort_cbc.h"
-
-/* for check. */
-void *mustbefreed;
-
-__code  returner(stack sp)
-{
-	framep fp = (framep)sp;
-	sp += fp->size;
-	goto fp->ret(fp->interface, sp);
-}
-
-__code  quicksort_start(void *arg, stack sp)
-{
-	QS_IF *recvif = arg;
-	int a,b,c,p;
-	a = recvif->v[recvif->s];
-	b = recvif->v[recvif->e];
-	c = recvif->v[(recvif->s+recvif->e)/2];
-
-	//printf("quicksort_start: s=%d,e=%d", recvif->s, recvif->e);
-	if (recvif->e <= recvif->s) goto returner(sp);
-
-	if (a < b) {
-		if (b < c)
-			p = b;
-		else if (a < c)
-			p = c;
-		else 
-			p = a;
-	} else {
-		if (a < c)
-			p = a;
-		else if (b < c)
-			p = c;
-		else 
-			p = b;
-	}
-
-	goto quicksort_divider (recvif, recvif->s, recvif->e, p, sp);
-}
-/* main routine end. */
-
-/* divide routine. */
-__code  quicksort_divider(QS_IF *recvif, int s, int e, int p, stack sp)
-{
-	goto quicksort_divider_s(recvif, s, e, p, sp);
-}
-__code  quicksort_divider_s(QS_IF *recvif, int s, int e, int p, stack sp)
-{
-	if (recvif->v[s]<p) {
-		goto quicksort_divider_s(recvif, s+1, e, p, sp);
-	} else
-		goto quicksort_divider_e(recvif, s, e, p, sp);
-}
-__code  quicksort_divider_e(QS_IF *recvif, int s, int e, int p, stack sp)
-{
-	if (p<recvif->v[e]) {
-		e--;
-		goto quicksort_divider_e(recvif, s, e, p, sp);
-	} else
-		goto quicksort_swapper(recvif, s, e, p, sp);
-}
-__code  quicksort_swapper(QS_IF *recvif, int s, int e, int p, stack sp)
-{
-	if (s<e) {
-		int tmp;
-		tmp = recvif->v[s];
-		recvif->v[s] = recvif->v[e];
-		recvif->v[e] = tmp;
-		goto quicksort_divider(recvif, s+1, e-1, p, sp);
-	} else {
-		goto quicksort_treecall(recvif, s, e, sp);
-	}
-}
-/* divide routin end. */
-
-
-/* recursive call routine. */
-__code  quicksort_treecall(QS_IF *recvif, int s, int e, stack sp)
-{
-	framep fp;
-	QS_IF *outif;
-
-	/* interface for first quicksort_start this segment directly jump to.  */
-	outif = (sp-=sizeof(QS_IF));
-	outif->v = recvif->v;
-	outif->s = recvif->s;
-	outif->e = e;
-	fp = (sp-=sizeof(frame));
-	fp->ret = quicksort_start;
-	fp->interface = recvif;
-	fp->size = sizeof(frame)+sizeof(QS_IF);
-
-	/* recvif is used by second quicksort_start.  */
-	recvif->s = e+1;
-	goto quicksort_start(outif, sp);
-}
-/* recursive call routine end. */
-
-#define STACK_SIZE 10240
-
-typedef struct {
-	__code  (*ret)(void*);
-	void *ret_arg;
-	stack *sp;
-} QS_FINISH;
-__code 
-quicksort(int *v, int s, int e,  RET ret, void *arg )
-{
-	framep fp;
-	stack sp0, sp;
-	sp0 = mustbefreed = malloc(STACK_SIZE);
-	sp = sp0 + STACK_SIZE;
-	QS_FINISH *finish_if;
-	QS_IF *outif;
-	
-	/* interface for quicksort_finish.  */
-	finish_if = (sp -= sizeof(QS_FINISH));
-	finish_if->ret = ret;
-	finish_if->ret_arg = arg;
-	finish_if->sp = sp0;
-
-	/* interface for quicksort_start.  */
-	outif = (sp -= sizeof(QS_IF));
-	outif->v = v;
-	outif->s = s;
-	outif->e = e;
-	/* frame for quicksort_finish.  */
-	fp = (sp -= sizeof(frame));
-	fp->ret = quicksort_finish;
-	fp->interface = finish_if;
-	fp->size = sizeof(frame)+sizeof(QS_IF);
-
-	goto quicksort_start(outif, sp);
-}
-__code 
-quicksort_finish(void *arg, stack sp)
-{
-	QS_FINISH interface;
-	interface = *(QS_FINISH*)arg;
-	//assert((void*)interface.sp==(void*)mustbefreed);
-	free(interface.sp);
-	goto interface.ret(interface.ret_arg);
-}
-
-
-
-#if 0
-void
-quicksort_c(int *v, int s0, int e0, stack sp)
-{
-	int p;
-	int s=s0, e=e0;
-	if (e<=s) return;
-
-	//p = (v[s]+v[(s+e)/2]+v[e])/3;
-	p = mid_point(v[s],v[e],v[(s+e)/2]);
-
-	while (1) {
-		 while (v[s]<p) s++;
-		 while (p<v[e]) e--;
-
-		 if (!(s<e)) break;
-		 SWAP(&v[s], &v[e]);
-		 s++; e--;
-	}
-	assert(e+1==s || s==e);
-
-	quicksort(v, s0, e);
-	quicksort(v, e+1, e0);
-	return;
-}
-
-
-
-/*  --------------------
- *     | args |fp| 
- *  --------------------
- *  +            ↑     -
- *               sp
- */ 
-/* ret segmentへgotoしたときのstack spの状態
- *
- * sp が直接さすのは frame 構造体
- * frame.size:
- * frame.ret: そのret segmentが終了した時にgotoすべきret segment.
- * frame.interface: frame.retへgotoするときのinterface.
- *                  このポインタが指すメモリ領域は stack
- *                  中にあっても良いしなくても良い。
- *                  ただしframe.retを登録した側で解放すべき。
- * sp+sizeof(frame)が指すのは実行中のret segmentのinterface(引数)
- * これは実行中のret segmentがメモリ管理する
- * 通常はこのret segmentが終了する際に sp+=frame.size とすればよい
- */
-__code caller0(void *arg, stack sp)
-{
-	/* interface for caller_finish0.  */
-	double *finish_arg = (sp -= sizeof(double));
-
-	/* arg for quicksort_start.  */
-	outif = (sp -= sizeof(*outif));
-	framep fp = (sp -= sizeof(frame));
-	fp->ret = caller_finish;
-	fp->interface = NULL;
-	fp->size = sizeof(*outif)+sizeof(frame);
-
-	goto quicksort_start(outif, sp);
-}
-__code caller_finish0(void *arg, stack sp)
-{
-}
-
-__code __returner0(void *arg , stack sp)
-{
-	framep fp = sp;
-	sp += fp->size;
-	goto fp->ret(fp->interface, sp);
-}
-
-#endif
-
-
-
-
--- a/quicksort_for_ppc/quicksort_cbc.h	Tue Feb 16 14:35:36 2010 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,26 +0,0 @@
-/* defined in file quicksort_cbc.cbc at offset 354  */
-__code  returner (stack sp);
-
-/* defined in file quicksort_cbc.cbc at offset 462  */
-__code  quicksort_start (void *arg, stack sp);
-
-/* defined in file quicksort_cbc.cbc at offset 1031  */
-__code  quicksort_divider (QS_IF *recvif, int s, int e, int p, stack sp);
-
-/* defined in file quicksort_cbc.cbc at offset 1155  */
-__code  quicksort_divider_s (QS_IF *recvif, int s, int e, int p, stack sp);
-
-/* defined in file quicksort_cbc.cbc at offset 1364  */
-__code  quicksort_divider_e (QS_IF *recvif, int s, int e, int p, stack sp);
-
-/* defined in file quicksort_cbc.cbc at offset 1576  */
-__code  quicksort_swapper (QS_IF *recvif, int s, int e, int p, stack sp);
-
-/* defined in file quicksort_cbc.cbc at offset 1916  */
-__code  quicksort_treecall (QS_IF *recvif, int s, int e, stack sp);
-
-/* defined in file quicksort_cbc.cbc at offset 2547  */
-__code  quicksort (int *v, int s, int e,  RET ret, void *arg );
-
-/* defined in file quicksort_cbc.cbc at offset 3213  */
-__code  quicksort_finish (void *arg, stack sp);
--- a/quicksort_for_ppc/quicksort_cbc2.cbc	Tue Feb 16 14:35:36 2010 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,159 +0,0 @@
-#include<stdio.h>
-#include<stdlib.h>
-#include<assert.h>
-
-typedef struct {
-	int *v;
-	int s;
-	int e;
-} QS_IF;
-
-typedef void *stack;
-typedef __code (*RET)(QS_IF, stack);
-typedef struct {
-	int size;
-	QS_IF interface;
-	RET ret;
-} frame, *framep;
-
-typedef __code (*RETTYPE)(void*);
-typedef struct {
-	RETTYPE ret;
-	void *ret_arg;
-	stack *sp;
-} QS_FINISH;
-#define STACK_SIZE 10240
-
-#include"quicksort_cbc2.h"
-
-__code returner(stack sp)
-{
-	framep fp = (framep)sp;
-	sp += fp->size;
-	goto fp->ret(fp->interface, sp);
-}
-
-__code quicksort_start(QS_IF recvif, stack sp)
-{
-	int a,b,c,p;
-	a = recvif.v[recvif.s];
-	b = recvif.v[recvif.e];
-	c = recvif.v[(recvif.s+recvif.e)/2];
-
-	//printf("quicksort_start: s=%d,e=%d", recvif->s, recvif->e);
-	if (recvif.e <= recvif.s) goto returner(sp);
-
-	if (a < b) {
-		if (b < c)
-			p = b;
-		else if (a < c)
-			p = c;
-		else 
-			p = a;
-	} else {
-		if (a < c)
-			p = a;
-		else if (b < c)
-			p = c;
-		else 
-			p = b;
-	}
-
-	goto quicksort_divider (recvif, recvif.s, recvif.e, p, sp);
-}
-/* main routine end. */
-
-/* divide routine. */
-__code quicksort_divider(QS_IF recvif, int s, int e, int p, stack sp)
-{
-	goto quicksort_divider_s(recvif, s, e, p, sp);
-}
-__code quicksort_divider_s(QS_IF recvif, int s, int e, int p, stack sp)
-{
-	if (recvif.v[s]<p) {
-		s++;
-		goto quicksort_divider_s(recvif, s, e, p, sp);
-	} else
-		goto quicksort_divider_e(recvif, s, e, p, sp);
-}
-__code quicksort_divider_e(QS_IF recvif, int s, int e, int p, stack sp)
-{
-	if (p<recvif.v[e]) {
-		e--;
-		goto quicksort_divider_e(recvif, s, e, p, sp);
-	} else
-		goto quicksort_swapper(recvif, s, e, p, sp);
-}
-__code quicksort_swapper(QS_IF recvif, int s, int e, int p, stack sp)
-{
-	if (s<e) {
-		int tmp;
-		tmp = recvif.v[s];
-		recvif.v[s] = recvif.v[e];
-		recvif.v[e] = tmp;
-		s++;
-		e--;
-		goto quicksort_divider(recvif, s, e, p, sp);
-	} else {
-		//assert(e+1==s || s==e);
-		goto quicksort_treecall(recvif, s, e, sp);
-	}
-}
-/* divide routin end. */
-
-
-/* recursive call routine. */
-__code quicksort_treecall(QS_IF recvif, int s, int e, stack sp)
-{
-	framep fp;
-
-	/* interface for first quicksort_start this segment directly jump to.  */
-	fp = (sp-=sizeof(frame));
-	fp->ret = quicksort_start;
-	fp->size = sizeof(frame);
-	fp->interface.v = recvif.v;
-	fp->interface.s = e+1;
-	fp->interface.e = recvif.e;
-
-	/* recvif is used by second quicksort_start.  */
-	recvif.e = e;
-	goto quicksort_start(recvif, sp);
-}
-/* recursive call routine end. */
-
-__code
-quicksort(int *v, int s, int e,  RETTYPE ret, void *arg )
-{
-	framep fp;
-	stack sp0, sp;
-	sp0 = malloc(STACK_SIZE);
-	printf("allocate a stack %p\n", sp0);
-	sp = sp0 + STACK_SIZE;
-	QS_FINISH *finish_if;
-	
-	/* interface for quicksort_finish.  */
-	finish_if = (sp -= sizeof(*finish_if));
-	finish_if->ret = ret;
-	finish_if->ret_arg = arg;
-	finish_if->sp = sp0;
-
-	/* interface for quicksort_start.  */
-	/* frame for quicksort_finish.  */
-	fp = (sp -= sizeof(frame));
-	fp->ret = quicksort_finish;
-	fp->size = sizeof(frame);
-	fp->interface.v = v;
-	fp->interface.s = s;
-	fp->interface.e = e;
-
-	goto quicksort_start(fp->interface, sp);
-}
-__code
-quicksort_finish(QS_IF recvif, stack sp)
-{
-	QS_FINISH *interface = (QS_FINISH*)sp;
-	free(interface->sp);
-	printf("free the stack %p\n", interface->sp);
-	goto interface->ret(interface->ret_arg);
-}
-
--- a/quicksort_for_ppc/quicksort_cbc2.h	Tue Feb 16 14:35:36 2010 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,27 +0,0 @@
-/* defined in file quicksort_cbc2.cbc at offset 402  */
-__code returner (stack sp);
-
-/* defined in file quicksort_cbc2.cbc at offset 509  */
-__code quicksort_start (QS_IF recvif, stack sp);
-
-/* defined in file quicksort_cbc2.cbc at offset 1047  */
-__code quicksort_divider (QS_IF recvif, int s, int e, int p, stack sp);
-
-/* defined in file quicksort_cbc2.cbc at offset 1169  */
-__code quicksort_divider_s (QS_IF recvif, int s, int e, int p, stack sp);
-
-/* defined in file quicksort_cbc2.cbc at offset 1380  */
-__code quicksort_divider_e (QS_IF recvif, int s, int e, int p, stack sp);
-
-/* defined in file quicksort_cbc2.cbc at offset 1589  */
-__code quicksort_swapper (QS_IF recvif, int s, int e, int p, stack sp);
-
-/* defined in file quicksort_cbc2.cbc at offset 1961  */
-__code quicksort_treecall (QS_IF recvif, int s, int e, stack sp);
-
-/* defined in file quicksort_cbc2.cbc at offset 2417  */
-__code quicksort (int *v, int s, int e,  RETTYPE ret, void *arg );
-
-/* defined in file quicksort_cbc2.cbc at offset 3052  */
-__code quicksort_finish (QS_IF recvif, stack sp);
-
--- a/quicksort_for_ppc/quicksort_cbc_inter.cbc	Tue Feb 16 14:35:36 2010 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,102 +0,0 @@
-
-#include<stdlib.h>
-typedef void *stack;
-typedef struct {
-	int size;
-	void *interface;
-	__code  (*ret)(void*, stack) ;
-} frame, *framep;
-
-/* quickstart main routine. */
-typedef struct {
-	int *v;
-	int s;
-	int e;
-} QS_IF ;
-typedef __code  (*RET)(void*);
-
-#include"quicksort_cbc.h"
-
-
-typedef struct {
-	__code  (*ret)(void*);
-	void *ret_arg;
-	stack *sp;
-} QS_FINISH;
-
-extern int *IFv;
-extern int IFs;
-extern int IFe;
-extern RET IFret;
-extern void *IFarg;
-extern stack IFsp;
-extern int IFsize;
-
-static void(*exitfunc)(void*);
-__code exitter(void *arg) {
-	exitfunc(arg);
-}
-
-__code quicksort_finish_IF(void *arg, stack sp);
-
-void
-quicksort_IF()
-{
-	printf("v=%p\n", IFv);
-	printf("s=%d\n", IFs);
-	printf("e=%d\n", IFe);
-	printf("ret=%p\n", IFret);
-	printf("arg=%p\n", IFarg);
-	printf("sp=%p\n", IFsp);
-	printf("size=%d\n", IFsize);
-	exitfunc = IFret;
-
-	goto quicksort_IF0(IFv, IFs, IFe, exitter, IFarg, IFsp, IFsize);
-}
-
-__code 
-quicksort_IF0(int *v, int s, int e,  RET ret, void *arg, stack sp0,int size)
-{
-	framep fp;
-	stack sp;
-	sp = sp0 + size;
-	QS_FINISH *finish_if;
-	QS_IF *outif;
-
-	printf("v=%p\n", v);
-	printf("s=%d\n", s);
-	printf("e=%d\n", e);
-	printf("ret=%p\n", ret);
-	printf("arg=%p\n", arg);
-	printf("sp=%p\n", sp0);
-	printf("size=%d\n", size);
-	
-	/* interface for quicksort_finish.  */
-	finish_if = (sp -= sizeof(QS_FINISH));
-	finish_if->ret = ret;
-	finish_if->ret_arg = arg;
-	finish_if->sp = sp0;
-
-	/* interface for quicksort_start.  */
-	outif = (sp -= sizeof(QS_IF));
-	outif->v = v;
-	outif->s = s;
-	outif->e = e;
-	/* frame for quicksort_finish.  */
-	fp = (sp -= sizeof(frame));
-	fp->ret = quicksort_finish_IF;
-	fp->interface = finish_if;
-	fp->size = sizeof(frame)+sizeof(QS_IF);
-
-	goto quicksort_start(outif, sp);
-}
-
-__code 
-quicksort_finish_IF(void *arg, stack sp)
-{
-	QS_FINISH interface;
-	interface = *(QS_FINISH*)arg;
-	//assert((void*)interface.sp==(void*)mustbefreed);
-	goto interface.ret(interface.ret_arg);
-}
-
--- a/quicksort_for_ppc/quicksort_test.cbc	Tue Feb 16 14:35:36 2010 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,129 +0,0 @@
-#include<stdio.h>
-#include<stdlib.h>
-#include<assert.h>
-#include<unistd.h>
-
-#include"quicksort_test.h"
-
-#define STACK_SIZE 10240
-
-extern void quicksort_IF();
-
-
-void
-random_initialize(int *v, int size, int min, int max)
-{
-	int i;
-	int diff = max-min+1;
-
-	for (i=0; i<size; i++) {
-		v[i] = min+random()%diff;
-	}
-	return;
-}
-
-static void
-print_array(int *v, int size)
-{
-	int i;
-	printf("[");
-	for (i=0; i<size; i++) {
-		printf("%s%4d", (i%10==0)? "\n  ":" ", v[i]);
-	}
-	printf(" ]\n");
-}
-
-int *IFv;
-int IFs;
-int IFe;
-void* IFret;
-void *IFarg;
-void* IFsp;
-int IFsize;
-
-void
-starter(int size)
-{
-	int *target;
-	void *sp;
-
-	target = (int*)malloc(sizeof(int)*size);
-	if (!target) {
-		perror("malloc");
-		exit(1);
-	}
-
-	random_initialize(target, size, 0, 90);
-
-	sp = malloc(STACK_SIZE);
-	if (!sp) {
-		perror("malloc");
-		exit(1);
-	}
-	//print_array(target, size);
-	//goto quicksort(target, 0, size-1, exit0, (void*)target);
-	IFv=   target;
-	IFs=    0;
-	IFe=    size-1;
-	IFret=  exit0;
-	IFarg=(void*)target;
-	IFsp= sp;
-	IFsize= STACK_SIZE;
-	quicksort_IF();
-
-	printf("bad region\n");
-}
-
-static int size=100;
-
-int
-main(int argc, char **argv)
-{
-	unsigned int seed=0;
-	int opt;
-
-	while ((opt = getopt(argc, argv, "s:n:")) != -1) {
-		switch (opt) {
-			case 's':
-				seed = atoi(optarg);
-				break;
-			case 'n':
-				size = atoi(optarg);
-				break;
-			default:
-				fprintf(stderr, "Usage: %s [-t times] [-n sizeofarray] [-s seed]\n", argv[0]);
-				exit(1);
-		}
-	}
-
-	srandom(seed);
-	starter(size);
-	return 0;
-}
-
-static int
-check_sort(int *v, int size)
-{
-	int i;
-	for (i=0; i<size-1; i++) {
-		if (v[i] > v[i+1])
-			return 0;
-	}
-	return 1;
-}
-
-void
-exit0(void *arg)
-{
-	int b;
-	//print_array(arg, size);
-	b = check_sort(arg, size);
-	if (b) {
-		printf("sorting successful!\n");
-		exit(EXIT_SUCCESS);
-	} else {
-		printf("sorting failure! \n");
-		exit(EXIT_FAILURE);
-	}
-}
-
--- a/quicksort_for_ppc/quicksort_test.h	Tue Feb 16 14:35:36 2010 +0900
+++ /dev/null	Thu Jan 01 00:00:00 1970 +0000
@@ -1,18 +0,0 @@
-/* defined in file quicksort_test.cbc at offset 160  */
-void random_initialize (int *v, int size, int min, int max);
-
-/* defined in file quicksort_test.cbc at offset 322  */
-static void print_array (int *v, int size);
-
-/* defined in file quicksort_test.cbc at offset 564  */
-void starter (int size);
-
-/* defined in file quicksort_test.cbc at offset 1095  */
-int main (int argc, char **argv);
-
-/* defined in file quicksort_test.cbc at offset 1491  */
-static int check_sort (int *v, int size);
-
-/* defined in file quicksort_test.cbc at offset 1620  */
-void exit0 (void *arg);
-