Mercurial > hg > Game > Cerium

changeset 1242:9d37fa6bc1da draft

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add Miller_Rabin
author Daichi Toma <amothic@gmail.com>
date Tue, 01 Nov 2011 19:01:13 +0900
parents b96b1604ab85
children 9df036b11eae
files example/Miller_Rabin/Func.h example/Miller_Rabin/Makefile example/Miller_Rabin/Makefile.cell example/Miller_Rabin/Makefile.def example/Miller_Rabin/Makefile.linux example/Miller_Rabin/Makefile.macosx example/Miller_Rabin/README example/Miller_Rabin/main.cc example/Miller_Rabin/ppe/Prime.cc example/Miller_Rabin/ppe/Prime.h example/Miller_Rabin/ppe/PrintTask.cc example/Miller_Rabin/ppe/PrintTask.h example/Miller_Rabin/ppe/task_init.cc example/Miller_Rabin/spe/Makefile example/Miller_Rabin/spe/Prime.cc example/Miller_Rabin/spe/Prime.h example/Miller_Rabin/spe/PrintTask.cc example/Miller_Rabin/spe/PrintTask.h example/Miller_Rabin/spe/spe-main.cc
diffstat 19 files changed, 563 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/Miller_Rabin/Func.h	Tue Nov 01 19:01:13 2011 +0900
@@ -0,0 +1,5 @@
+enum {
+#include "SysTasks.h"
+	Prime,
+	PrintTask,
+};
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/Miller_Rabin/Makefile	Tue Nov 01 19:01:13 2011 +0900
@@ -0,0 +1,24 @@
+default: macosx
+
+macosx: FORCE
+	@echo "Make for Mac OS X"
+	@$(MAKE) -f Makefile.macosx
+
+fifo64: FORCE
+	@echo "Make for Mac OS X 64bit mode"
+	@$(MAKE) -f Makefile.macosx ABIBIT=64
+
+linux: FORCE
+	@echo "Make for Linux"
+	@$(MAKE) -f Makefile.linux
+
+cell: FORCE
+	@echo "Make for PS3 (Cell)"
+	@$(MAKE) -f Makefile.cell
+
+FORCE:
+
+clean:
+	@$(MAKE) -f Makefile.macosx clean
+	@$(MAKE) -f Makefile.linux clean
+	@$(MAKE) -f Makefile.cell clean
\ No newline at end of file
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/Miller_Rabin/Makefile.cell	Tue Nov 01 19:01:13 2011 +0900
@@ -0,0 +1,45 @@
+include ./Makefile.def
+
+ABIBIT=32
+CFLAGS += -m$(ABIBIT)  -D__CERIUM_CELL__
+
+SRCS_TMP = $(wildcard *.cc)
+SRCS_EXCLUDE =  # 除外するファイルを書く
+SRCS = $(filter-out $(SRCS_EXCLUDE),$(SRCS_TMP))
+OBJS = $(SRCS:.cc=.o)
+
+TASK_DIR  = ppe
+TASK_SRCS_TMP = $(wildcard $(TASK_DIR)/*.cc)
+TASK_SRCS_EXCLUDE = 
+TASK_SRCS = $(filter-out $(TASK_DIR)/$(TASK_SRCS_EXCLUDE),$(TASK_SRCS_TMP))
+TASK_OBJS = $(TASK_SRCS:.cc=.o)
+
+LIBS += -lCellManager -lspe2 -lpthread -Wl,--gc-sections 
+
+.SUFFIXES: .cc .o
+
+.cc.o:
+	$(CC) $(CFLAGS) $(INCLUDE) -c $< -o $@
+
+all: $(TARGET) speobject
+
+$(TARGET): $(OBJS) $(TASK_OBJS)
+	$(CC) $(CFLAGS) -o $@ $(OBJS) $(TASK_OBJS) $(LIBS)
+
+speobject:
+	cd spe; $(MAKE) ABIBIT=$(ABIBIT)
+
+run:
+	./$(TARGET) -cpu 6 
+
+link:
+	$(CC) -o $(TARGET) $(OBJS) $(TASK_OBJS) $(LIBS)
+
+debug: $(TARGET)
+	sudo ppu-gdb ./$(TARGET) 
+
+clean:
+	rm -f $(TARGET) $(OBJS) $(TASK_OBJS)
+	rm -f *~ \#*
+	rm -f ppe/*~ ppe/\#*
+	cd spe; $(MAKE) clean
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/Miller_Rabin/Makefile.def	Tue Nov 01 19:01:13 2011 +0900
@@ -0,0 +1,15 @@
+TARGET = prime
+
+# include/library path
+# ex  macosx
+#CERIUM = /Users/gongo/Source/Cerium
+
+# ex  linux/ps3
+CERIUM = ../../../Cerium
+
+CC      = g++
+#CFLAGS  = -O9 -Wall
+CFLAGS  = -g -Wall
+
+INCLUDE = -I${CERIUM}/include/TaskManager -I. -I..
+LIBS = -L${CERIUM}/TaskManager
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/Miller_Rabin/Makefile.linux	Tue Nov 01 19:01:13 2011 +0900
@@ -0,0 +1,36 @@
+include ./Makefile.def
+
+SRCS_TMP = $(wildcard *.cc)
+SRCS_EXCLUDE =  # 除外するファイルを書く
+SRCS = $(filter-out $(SRCS_EXCLUDE),$(SRCS_TMP))
+OBJS = $(SRCS:.cc=.o)
+
+TASK_DIR  = ppe
+TASK_SRCS_TMP = $(wildcard $(TASK_DIR)/*.cc)
+TASK_SRCS_EXCLUDE = 
+TASK_SRCS = $(filter-out $(TASK_DIR)/$(TASK_SRCS_EXCLUDE),$(TASK_SRCS_TMP))
+TASK_OBJS = $(TASK_SRCS:.cc=.o)
+
+LIBS += -lFifoManager
+
+.SUFFIXES: .cc .o
+
+.cc.o:
+	$(CC) $(CFLAGS) $(INCLUDE) -c $< -o $@
+
+all: $(TARGET)
+
+$(TARGET): $(OBJS) $(TASK_OBJS)
+	$(CC) -o $@ $(OBJS) $(TASK_OBJS) $(LIBS)
+
+link:
+	$(CC) -o $(TARGET) $(OBJS) $(TASK_OBJS) $(LIBS)
+
+debug: $(TARGET)
+	sudo gdb ./$(TARGET) 
+
+clean:
+	rm -f $(TARGET) $(OBJS) $(TASK_OBJS)
+	rm -f *~ \#*
+	rm -f ppe/*~ ppe/\#*
+	rm -f spe/*~ spe/\#*
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/Miller_Rabin/Makefile.macosx	Tue Nov 01 19:01:13 2011 +0900
@@ -0,0 +1,36 @@
+include ./Makefile.def
+
+SRCS_TMP = $(wildcard *.cc)
+SRCS_EXCLUDE =  # 除外するファイルを書く
+SRCS = $(filter-out $(SRCS_EXCLUDE),$(SRCS_TMP))
+OBJS = $(SRCS:.cc=.o)
+
+TASK_DIR  = ppe
+TASK_SRCS_TMP = $(wildcard $(TASK_DIR)/*.cc)
+TASK_SRCS_EXCLUDE = 
+TASK_SRCS = $(filter-out $(TASK_DIR)/$(TASK_SRCS_EXCLUDE),$(TASK_SRCS_TMP))
+TASK_OBJS = $(TASK_SRCS:.cc=.o)
+
+LIBS += -lFifoManager `sdl-config --libs`
+
+.SUFFIXES: .cc .o
+
+.cc.o:
+	$(CC) $(CFLAGS) $(INCLUDE) -c $< -o $@
+
+all: $(TARGET)
+
+$(TARGET): $(OBJS) $(TASK_OBJS)
+	$(CC) -o $@ $(OBJS) $(TASK_OBJS) $(LIBS)
+
+link:
+	$(CC) -o $(TARGET) $(OBJS) $(TASK_OBJS) $(LIBS)
+
+debug: $(TARGET)
+	sudo gdb ./$(TARGET) 
+
+clean:
+	rm -f $(TARGET) $(OBJS) $(TASK_OBJS)
+	rm -f *~ \#*
+	rm -f ppe/*~ ppe/\#*
+	rm -f spe/*~ spe/\#*
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/Miller_Rabin/README	Tue Nov 01 19:01:13 2011 +0900
@@ -0,0 +1,16 @@
+- 概要
+
+指定された範囲の素数を計算するプログラムです。
+
+- 実行方法
+
+% ./prime [-num number] [-print]
+
+  -num		出力する素数の範囲   
+  -print	計算した素数を出力
+
+- 実行例 (-cpu は Cerium 標準のオプションです)
+
+% ./prime -num 100 -print -cpu 6
+0 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 
+
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/Miller_Rabin/main.cc	Tue Nov 01 19:01:13 2011 +0900
@@ -0,0 +1,87 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include "TaskManager.h"
+#include "Func.h"
+
+typedef unsigned long long U64;
+
+/* task_initを宣言 */
+extern void task_init(void);
+
+/* TaskManagerを宣言 */
+extern TaskManager *manager;
+
+static U64 num = 1000;
+static bool print_flag = false;
+
+/* help文章 */
+const char *usr_help_str = "Usage: ./prime [-cpu spe_num] [-num N]\n\
+							-cpu    Number of SPE (default 1) \n\
+							-num	Caluculate of Prime scope (default 1000 * 1000 * 1000) ";
+
+	int
+init(int argc, char **argv)
+{
+	for (int i = 1; argv[i]; ++i) {
+		if (strcmp(argv[i], "-num") == 0) {
+			num = atoi(argv[++i]);
+		}
+		else if (strcmp(argv[i], "-print") == 0) {
+			print_flag = true;
+		}
+	}
+	return 0;
+}
+
+	void
+prime_init(TaskManager *manager)
+{
+
+	U64 div_size = 1000;
+	U64 task_num = ((num >> 1) + div_size - 1) / div_size;
+
+	bool *output = (bool*)manager->allocate(sizeof(bool)*task_num*div_size); /* 判定結果を収める配列 */
+
+	HTask *print = manager->create_task(PrintTask);
+
+	for (U64 i = 0; i < task_num; i++) {
+
+		HTask *prime = manager->create_task(Prime);
+
+		prime->set_outData(0,&output[i*div_size],sizeof(bool)*div_size);
+
+		prime->set_cpu(SPE_ANY);
+
+		prime->set_param(0,(memaddr)(i*div_size));		// 開始地点
+		prime->set_param(1,(memaddr)((i+1)*div_size - 1));	// 終了地点
+
+		print->wait_for(prime);
+
+		prime->spawn();
+	}
+
+	/* 出力用のタスクに判定結果を収めた配列を渡す */ 
+	print->set_inData(0,output,sizeof(bool)*task_num*div_size);
+	/* 出力する数を渡す */
+	print->set_param(0,(memaddr)num);
+	/* printするかどうかを渡す */
+	print->set_param(1,(memaddr)print_flag);
+	/* PPEを使うように指示 */
+	print->set_cpu(CPU_PPE);
+	/* タスクを登録 */
+	print->spawn();
+}
+
+	int
+TMmain(TaskManager *manager, int argc, char *argv[])
+{
+	if (init(argc, argv) < 0) {
+		return -1;
+	}
+
+	task_init();
+	prime_init(manager);
+
+	return 0;
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/Miller_Rabin/ppe/Prime.cc	Tue Nov 01 19:01:13 2011 +0900
@@ -0,0 +1,80 @@
+#include <stdio.h>
+#include "SchedTask.h"
+#include "Prime.h"
+#include "Func.h"
+
+typedef unsigned long long U64;
+
+static U64 base[] = { 2, 3, 5, 7, 11 };
+#define MRMAX 5
+
+SchedDefineTask1(Prime, prime);
+
+static U64
+powMod(U64 base, U64 power, U64 mod)
+{
+	U64 result = 1;
+
+	while (power > 0) {
+		if ( power & 1 == 1 ) {
+			result = (result * base) % mod;
+		}
+		base = ( base * base ) % mod;
+		power >>= 1;
+	}
+	return result;
+}
+
+static bool
+millarRabin(U64 a, U64 s, U64 d, U64 n) {
+	U64 x = powMod(a, d, n);
+	if ( x == 1) return true;
+	for ( U64 r = 0; r < s; r++) {
+		if ( x == n-1 ) return true;
+		x = (x * x) % n;
+	}
+	return false;
+}
+
+static bool
+isPrime(U64 n) {
+
+	if ( n <= 1 ) return false;
+
+	U64 d = n - 1;
+	U64 s = 0;
+
+	while( (d & 1) == 0 ) {
+		d >>= 1;
+		s++;
+	}
+
+	for ( int i = 0; i < MRMAX; i++ ) {
+		if ( n == base[i] ) return true;
+		if (!millarRabin(base[i], s, d, n)) return false;
+	}
+	return true;
+}
+
+	static int
+prime(SchedTask *smanager, void *rbuf, void *wbuf)
+{
+	U64 start = (U64)smanager->get_param(0);	/* 素数判定の開始地点 */
+	U64 end   = (U64)smanager->get_param(1);	/* 素数判定の終了地点 */
+	U64 range = end - start;					/* 判定する範囲		  */
+
+	/* 判定結果を収める配列を受け取る */
+	bool *output = (bool*)smanager->get_output(wbuf, 0);
+
+	/* 初期化 */
+	for (U64 i = 0; i < range; i++){
+		output[i] = true;
+	}
+
+	for (U64 i = start + 1,index = 0; index < range; i += 2, index++) {
+		if (!isPrime(i)) {
+			output[index]  =  false;
+		}
+	}
+	return 0;
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/Miller_Rabin/ppe/Prime.h	Tue Nov 01 19:01:13 2011 +0900
@@ -0,0 +1,6 @@
+#ifndef INCLUDED_TASK_PRIME
+#define INCLUDED_TASK_PRIME
+
+#include "SchedTask.h"
+
+#endif
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/Miller_Rabin/ppe/PrintTask.cc	Tue Nov 01 19:01:13 2011 +0900
@@ -0,0 +1,32 @@
+#include <stdio.h>
+#include "SchedTask.h"
+#include "PrintTask.h"
+#include "Func.h"
+
+typedef unsigned long long U64;
+
+SchedDefineTask1(PrintTask, print);
+
+	static int
+print(SchedTask *smanager, void *rbuf, void *wbuf)
+{
+	bool print_flag = (bool)smanager->get_param(1);		//プリントするかどうか
+
+	if (print_flag == false) {
+		return 0;
+	}
+
+	U64 size = ((U64)smanager->get_param(0)) >> 1;			/* 出力する範囲 */
+	bool *input = (bool*)smanager->get_input(rbuf, 0);	/* 出力する配列 */
+	
+	printf("%d ",(int)2);
+
+	/* 素数の判定結果が1ならば出力する */
+	for (U64 i = 1; i < size; i++) {
+		if ( input[i] == true ) {
+			printf("%llu ",i*2+1);
+		}
+	}
+	printf("\n");
+	return 0;
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/Miller_Rabin/ppe/PrintTask.h	Tue Nov 01 19:01:13 2011 +0900
@@ -0,0 +1,6 @@
+#ifndef INCLUDED_TASK_PRINTTASK
+#define INCLUDED_TASK_PRINTTASK
+
+#include "SchedTask.h"
+
+#endif
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/Miller_Rabin/ppe/task_init.cc	Tue Nov 01 19:01:13 2011 +0900
@@ -0,0 +1,12 @@
+#include "Func.h"
+#include "Scheduler.h"
+
+SchedExternTask(Prime);
+SchedExternTask(PrintTask);
+
+	void
+task_init()
+{
+	SchedRegister(Prime);
+	SchedRegister(PrintTask);
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/Miller_Rabin/spe/Makefile	Tue Nov 01 19:01:13 2011 +0900
@@ -0,0 +1,26 @@
+include ../Makefile.def
+
+TARGET = ../spe-main
+
+SRCS_TMP = $(wildcard *.cc)
+SRCS = $(filter-out $(SRCS_EXCLUDE),$(SRCS_TMP))
+OBJS = $(SRCS:.cc=.o)
+
+CC      = spu-g++  -D__CERIUM_CELL__ -DABIBIT=$(ABIBIT)
+CFLAGS  = -O9 -g -Wall -fno-exceptions -fno-rtti#-DDEBUG
+INCLUDE = -I../${CERIUM}/include/TaskManager -I. -I..
+LIBS = -L../${CERIUM}/TaskManager -lspemanager  -Wl,--gc-sections 
+
+.SUFFIXES: .cc .o
+
+.cc.o:
+	$(CC) $(CFLAGS) $(INCLUDE) -c $< -o $@
+
+all: $(TARGET)
+
+$(TARGET): $(OBJS)
+	$(CC) -o $@ $(OBJS) $(TASK_OBJS) $(LIBS)
+
+clean:
+	rm -f $(TARGET) $(OBJS)
+	rm -f *~ \#*
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/Miller_Rabin/spe/Prime.cc	Tue Nov 01 19:01:13 2011 +0900
@@ -0,0 +1,80 @@
+#include <stdio.h>
+#include "SchedTask.h"
+#include "Prime.h"
+#include "Func.h"
+
+typedef unsigned long long U64;
+
+static U64 base[] = { 2, 3, 5, 7, 11 };
+#define MRMAX 5
+
+SchedDefineTask1(Prime, prime);
+
+static U64
+powMod(U64 base, U64 power, U64 mod)
+{
+	U64 result = 1;
+
+	while (power > 0) {
+		if ( power & 1 == 1 ) {
+			result = (result * base) % mod;
+		}
+		base = ( base * base ) % mod;
+		power >>= 1;
+	}
+	return result;
+}
+
+static bool
+millarRabin(U64 a, U64 s, U64 d, U64 n) {
+	U64 x = powMod(a, d, n);
+	if ( x == 1) return true;
+	for ( U64 r = 0; r < s; r++) {
+		if ( x == n-1 ) return true;
+		x = (x * x) % n;
+	}
+	return false;
+}
+
+static bool
+isPrime(U64 n) {
+
+	if ( n <= 1 ) return false;
+
+	U64 d = n - 1;
+	U64 s = 0;
+
+	while( (d & 1) == 0 ) {
+		d >>= 1;
+		s++;
+	}
+
+	for ( int i = 0; i < MRMAX; i++ ) {
+		if ( n == base[i] ) return true;
+		if (!millarRabin(base[i], s, d, n)) return false;
+	}
+	return true;
+}
+
+	static int
+prime(SchedTask *smanager, void *rbuf, void *wbuf)
+{
+	U64 start = (U64)smanager->get_param(0);	/* 素数判定の開始地点 */
+	U64 end   = (U64)smanager->get_param(1);	/* 素数判定の終了地点 */
+	U64 range = end - start;					/* 判定する範囲		  */
+
+	/* 判定結果を収める配列を受け取る */
+	bool *output = (bool*)smanager->get_output(wbuf, 0);
+
+	/* 初期化 */
+	for (U64 i = 0; i < range; i++){
+		output[i] = true;
+	}
+
+	for (U64 i = start + 1,index = 0; index < range; i += 2, index++) {
+		if (!isPrime(i)) {
+			output[index]  =  false;
+		}
+	}
+	return 0;
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/Miller_Rabin/spe/Prime.h	Tue Nov 01 19:01:13 2011 +0900
@@ -0,0 +1,6 @@
+#ifndef INCLUDED_TASK_PRIME
+#define INCLUDED_TASK_PRIME
+
+#include "SchedTask.h"
+
+#endif
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/Miller_Rabin/spe/PrintTask.cc	Tue Nov 01 19:01:13 2011 +0900
@@ -0,0 +1,32 @@
+#include <stdio.h>
+#include "SchedTask.h"
+#include "PrintTask.h"
+#include "Func.h"
+
+typedef unsigned long long U64;
+
+SchedDefineTask1(PrintTask, print);
+
+	static int
+print(SchedTask *smanager, void *rbuf, void *wbuf)
+{
+	bool print_flag = (bool)smanager->get_param(1);		//プリントするかどうか
+
+	if (print_flag == false) {
+		return 0;
+	}
+
+	U64 size = ((U64)smanager->get_param(0)) >> 1;			/* 出力する範囲 */
+	bool *input = (bool*)smanager->get_input(rbuf, 0);	/* 出力する配列 */
+	
+	printf("%d ",(int)2);
+
+	/* 素数の判定結果が1ならば出力する */
+	for (U64 i = 1; i < size; i++) {
+		if ( input[i] == true ) {
+			printf("%llu ",i*2+1);
+		}
+	}
+	printf("\n");
+	return 0;
+}
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/Miller_Rabin/spe/PrintTask.h	Tue Nov 01 19:01:13 2011 +0900
@@ -0,0 +1,6 @@
+#ifndef INCLUDED_TASK_PRINTTASK
+#define INCLUDED_TASK_PRINTTASK
+
+#include "SchedTask.h"
+
+#endif
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/example/Miller_Rabin/spe/spe-main.cc	Tue Nov 01 19:01:13 2011 +0900
@@ -0,0 +1,13 @@
+#include "Func.h"
+#include "Scheduler.h"
+
+SchedExternTask(Prime);
+SchedExternTask(PrintTask);
+
+void
+task_init(Scheduler *s)
+{
+	SchedRegister(Prime);
+	SchedRegister(PrintTask);
+}
+