From fe8ecf773b5cfabf9b6a81d2d0c178c85d897103 Mon Sep 17 00:00:00 2001 From: adash Date: Wed, 17 Jun 2009 19:01:39 +0000 Subject: [PATCH] bug fix in Sort.java (carefully manipulate character pointer increment/decrement of C while converting into Java) --- .../src/Benchmarks/SingleTM/Bayes/Adtree.java | 2 + .../src/Benchmarks/SingleTM/Bayes/Data.java | 35 +-- Robust/src/Benchmarks/SingleTM/Bayes/Net.java | 4 +- .../src/Benchmarks/SingleTM/Bayes/Queue.java | 4 +- .../src/Benchmarks/SingleTM/Bayes/Random.java | 93 ++++++++ .../src/Benchmarks/SingleTM/Bayes/Sort.java | 205 ++++++++++-------- Robust/src/Benchmarks/SingleTM/Bayes/makefile | 2 +- 7 files changed, 240 insertions(+), 105 deletions(-) create mode 100644 Robust/src/Benchmarks/SingleTM/Bayes/Random.java diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/Adtree.java b/Robust/src/Benchmarks/SingleTM/Bayes/Adtree.java index 24be2441..d6c7cb3e 100644 --- a/Robust/src/Benchmarks/SingleTM/Bayes/Adtree.java +++ b/Robust/src/Benchmarks/SingleTM/Bayes/Adtree.java @@ -221,6 +221,7 @@ public class Adtree { int numVar = dataPtr.numVar; for (int v = (index + 1); v < numVar; v++) { + //System.out.println("DEBUG: v= " +v+ " numVar= " + numVar+ " calling makeVary"); AdtreeVary varyPtr = makeVary(parentIndex, v, start, numRecord, dataPtr); boolean status; @@ -230,6 +231,7 @@ public class Adtree { } } + //System.out.println("DEBUG: End of makeNode"); return nodePtr; } diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/Data.java b/Robust/src/Benchmarks/SingleTM/Bayes/Data.java index c33a5c81..de89697f 100644 --- a/Robust/src/Benchmarks/SingleTM/Bayes/Data.java +++ b/Robust/src/Benchmarks/SingleTM/Bayes/Data.java @@ -129,7 +129,7 @@ public class Data { int numThreshold = 1 << parentIdListPtr.list_getSize(); int[] thresholds = new int[numThreshold]; for (int t = 0; t < numThreshold; t++) { - int threshold = randomPtr.random_generate() % (DATA_PRECISION + 1); + int threshold = (int) (randomPtr.random_generate() % (DATA_PRECISION + 1)); thresholds[t] = threshold; } thresholdsTable[v] = thresholds; @@ -156,6 +156,7 @@ public class Data { while ((v = doneBitmapPtr.bitmap_findClear(v + 1)) >= 0) { IntList childIdListPtr = netPtr.net_getChildIdListPtr(v); int numChild = childIdListPtr.list_getSize(); + if (numChild == 0) { boolean status; @@ -166,19 +167,19 @@ public class Data { workQueuePtr.queue_clear(); if((status = workQueuePtr.queue_push(v)) != true) { - System.out.println("status= "+ status + "should be true"); + System.out.println("Assert failed: status= "+ status + "should be true"); System.exit(0); } while (!(workQueuePtr.queue_isEmpty())) { int id = workQueuePtr.queue_pop(); if((status = doneBitmapPtr.bitmap_set(id)) != true) { - System.out.println("status= "+ status + "should be true"); + System.out.println("Assert failed: status= "+ status + "should be true"); System.exit(0); } if((status = dependencyVectorPtr.vector_pushBack(id)) == false) { - System.out.println("status= "+ status + "should be true"); + System.out.println("Assert failed: status= "+ status + "should be true"); System.exit(0); } @@ -190,7 +191,7 @@ public class Data { it = it.nextPtr; int parentId = parentIdListPtr.list_iter_next(it); if((status = workQueuePtr.queue_push(parentId)) == false) { - System.out.println("status= "+ status + "should be true"); + System.out.println("Assert failed: status= "+ status + "should be true"); System.exit(0); } } @@ -212,7 +213,7 @@ public class Data { } if(numOrder != numVar) { - System.out.println("numVar should be equal to numOrder"); + System.out.println("Assert failed: numVar should be equal to numOrder"); System.exit(0); } @@ -228,24 +229,25 @@ public class Data { int index = 0; IntListNode it = parentIdListPtr.head; parentIdListPtr.list_iter_reset(it); + while (parentIdListPtr.list_iter_hasNext(it)) { it = it.nextPtr; int parentId = parentIdListPtr.list_iter_next(it); int value = records[startindex + parentId]; if(value == DATA_INIT) { - System.out.println("value should be != DATA_INIT"); + System.out.println("Assert failed value should be != DATA_INIT"); System.exit(0); } - //assert(value != DATA_INIT); + index = (index << 1) + value; } - int rnd = randomPtr.random_generate() % DATA_PRECISION; + int rnd = (int) (randomPtr.random_generate() % DATA_PRECISION); int threshold = thresholdsTable[v][index]; records[startindex + v] = (char) ((rnd < threshold) ? 1 : 0); } startindex += numVar; if(startindex > numRecord * numVar) { - System.out.println("value should be != DATA_INIT in data_generate()"); + System.out.println("Assert failed: value should be != DATA_INIT in data_generate()"); System.exit(0); } } @@ -306,14 +308,19 @@ public class Data { int num, int offset) { - if((start < 0) || (start > numRecord)) + if((start < 0) || (start > numRecord)) { System.out.println("start: Assert failed in data_sort"); - if((num < 0) || (num > numRecord)) + System.exit(0); + } + if((num < 0) || (num > numRecord)) { System.out.println("num: Assert failed in data_sort"); - if((start + num < 0) || (start + num > numRecord)) + System.exit(0); + } + if((start + num < 0) || (start + num > numRecord)) { System.out.println("start + num: Assert failed in data_sort"); + System.exit(0); + } - //FIXME Sort.sort(records, start * numVar, num, diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/Net.java b/Robust/src/Benchmarks/SingleTM/Bayes/Net.java index c6bdb411..d526a321 100644 --- a/Robust/src/Benchmarks/SingleTM/Bayes/Net.java +++ b/Robust/src/Benchmarks/SingleTM/Bayes/Net.java @@ -881,9 +881,9 @@ public class Net { for (int n = 0; n < numNode; n++) { for (int p = 0; p < maxNumParent; p++) { - int value = randomPtr.random_generate() % 100; + int value = (int) (randomPtr.random_generate() % 100); if (value < percentParent) { - int parent = randomPtr.random_generate() % numNode; + int parent = (int) (randomPtr.random_generate() % numNode); if ((parent != n) && !net_hasEdge(parent, n) && !net_isPath(n, parent, visitedBitmapPtr, workQueuePtr)) diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/Queue.java b/Robust/src/Benchmarks/SingleTM/Bayes/Queue.java index d67fcd02..9ee50a19 100644 --- a/Robust/src/Benchmarks/SingleTM/Bayes/Queue.java +++ b/Robust/src/Benchmarks/SingleTM/Bayes/Queue.java @@ -220,8 +220,8 @@ public class Queue { int i; int base = pop + 1; for (i = 0; i < numElement; i++) { - int r1 = randomPtr.random_generate() % numElement; - int r2 = randomPtr.random_generate() % numElement; + int r1 = (int) (randomPtr.random_generate() % numElement); + int r2 = (int) (randomPtr.random_generate() % numElement); int i1 = (base + r1) % capacity; int i2 = (base + r2) % capacity; int tmp = elements[i1]; diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/Random.java b/Robust/src/Benchmarks/SingleTM/Bayes/Random.java new file mode 100644 index 00000000..2c601f48 --- /dev/null +++ b/Robust/src/Benchmarks/SingleTM/Bayes/Random.java @@ -0,0 +1,93 @@ +public class Random { + long[] mt; + int mti; + long RANDOM_DEFAULT_SEED; + /* period parameter */ + int N; + int M; + long MATRIX_A; + long UPPER_MASK; + long LOWER_MASK; + + public Random() { + RANDOM_DEFAULT_SEED = 0L; + N = 624; + M = 397; + mt = new long[N]; + mti = N; + MATRIX_A = 0x9908b0dfL; /* constant vector a */ + UPPER_MASK = 0x80000000L; /* most significant w-r bits */ + LOWER_MASK = 0x7fffffffL; /* least significant r bits */ + } + + public void random_alloc() { + init_genrand(this.RANDOM_DEFAULT_SEED); + } + + /* initializes mt[N] with a seed */ + public void init_genrand(long s) { + int mti; + mt[0]= s & 0xFFFFFFFFL; + for (mti=1; mti> 30)) + mti); + /* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */ + /* In the previous versions, MSBs of the seed affect */ + /* only MSBs of the array mt[]. */ + /* 2002/01/09 modified by Makoto Matsumoto */ + mt[mti] &= 0xFFFFFFFFL; + /* for >32 bit machines */ + } + this.mti=mti; + } + + public void random_seed(long seed) { + init_genrand(seed); + } + + public long random_generate() { + return genrand_int32(); + } + + //public static long genrand_int32(long[] mt, long mtiPtr) { + public long genrand_int32() { + long y; + long[] mag01= new long[2]; + mag01[0] = 0x0L; + mag01[1] = MATRIX_A; + int mti = this.mti; + + /* mag01[x] = x * MATRIX_A for x=0,1 */ + + if (mti >= N) { /* generate N words at one time */ + int kk; + + if (mti == N+1) /* if init_genrand() has not been called, */ + init_genrand(5489L); /* a default initial seed is used */ + + for (kk=0;kk> 1) ^ mag01[(int)(y & 0x1L)]; + } + for (;kk> 1) ^ mag01[(int)(y & 0x1L)]; + } + y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK); + mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[(int)(y & 0x1L)]; + + mti = 0; + } + + y = mt[mti++]; + + /* Tempering */ + y ^= (y >> 11); + y ^= (y << 7) & 0x9d2c5680L; + y ^= (y << 15) & 0xefc60000L; + y ^= (y >> 18); + + this.mti = mti; + + return y; + } +} diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/Sort.java b/Robust/src/Benchmarks/SingleTM/Bayes/Sort.java index 6cc0dd77..623e7545 100644 --- a/Robust/src/Benchmarks/SingleTM/Bayes/Sort.java +++ b/Robust/src/Benchmarks/SingleTM/Bayes/Sort.java @@ -88,6 +88,7 @@ public class Sort { public Sort() { } + /* ============================================================================= * swap * ============================================================================= @@ -95,7 +96,7 @@ public class Sort { public static void swap (char[] base, int a, int b, int width) { - if (a != b) { + if (a != b ) { while (width--) { char tmp = base[a]; base[a++] = base[b]; @@ -109,27 +110,25 @@ public class Sort { * shortsort * ============================================================================= */ - public static void - shortsort (char[] base, - int lo, - int hi, - int width, - int n, - int offset) - { - while (hi > lo) { - int max = lo; - int p; - for (p = (lo + width); p <= hi; p += width) { - if (cmp(base, p, max, n, offset) > 0) { - max = p; - } + + public static void shortsort(char[] base, + int lo, + int hi, + int width, + int n, + int offset) + { + while(hi > lo) { + int max = lo; + for(int p = (lo + width); p <= hi; p += width) { + if(cmp(base, p, max, n, offset) > 0) { + max = p; } - swap(base, max, hi, width); - hi -= width; } + swap(base, max, hi, width); + hi -= width; } - + } /* ============================================================================= * sort @@ -143,6 +142,13 @@ public class Sort { int n, int offset) { + /** + * debug + **/ + /* + for(int o = 0; o< (width * (num - 1)); o++) + System.out.println("base["+ o +"]=" + (int)base[o]); + */ if (num < 2 || width == 0) { return; } @@ -152,96 +158,95 @@ public class Sort { * where to start looking in * the base array **/ - char[] lostk= new char[30]; - char[] histk= new char[30]; + int[] lostk= new int[30]; + int[] histk= new int[30]; int stkptr = 0; + start = 0; int lo = start; int hi = start + (width * (num - 1)); int size = 0; - /** - * debug - **/ - //System.out.println("start= " + start + " base.length= " + base.length + " hi= " + hi); + boolean cont = true; - recurse(base, lo, hi, width, n, offset, lostk, histk, stkptr, size); + ptrVal pv = new ptrVal(); + pv.lo = lo; + pv.hi = hi; + pv.width = width; + pv.n = n; + pv.offset = offset; - } + int typeflag; - public void recurse(char[] base, - int lo, - int hi, - int width, - int n, - int offset, - char[] lostk, - char[] histk, - int stkptr, - int size) - { + while(cont) { - size = (hi - lo) / width + 1; + size = (pv.hi - pv.lo) / pv.width + 1; + + /** + * debug + **/ + //System.out.println("DEBUG: lo= "+ pv.lo + " hi= " + pv.hi + " width= " + pv.width+ " offset= " + pv.offset + " n= " + pv.n + " size= " + size); - if (size <= CUTOFF) { + if (size <= CUTOFF) { - shortsort(base, lo, hi, width, n, offset); + shortsort(base, pv.lo, pv.hi, pv.width, pv.n, pv.offset); - } else { + } else { - int mid = lo + (size / 2) * width; - swap(base, mid, lo, width); + pv.mid = pv.lo + (size / 2) * pv.width; + swap(base, pv.mid, pv.lo, pv.width); - int loguy = lo; - int higuy = hi + width; + pv.loguy = pv.lo; + pv.higuy = pv.hi + pv.width; - boolean status = true; - while(true) { - do { - loguy += width; - } while (loguy <= hi && cmp(base, loguy, lo, n, offset) <= 0); - do { - higuy -= width; - } while (higuy > lo && cmp(base, higuy, lo, n, offset) >= 0); - if (higuy < loguy) { - break; + while(true) { + do { + pv.loguy += pv.width; + } while (pv.loguy <= pv.hi && cmp(base, pv.loguy, pv.lo, pv.n, pv.offset) <= 0); + do { + pv.higuy -= pv.width; + } while (pv.higuy > pv.lo && cmp(base, pv.higuy, pv.lo, pv.n, pv.offset) >= 0); + if (pv.higuy < pv.loguy) { + break; + } + swap(base, pv.loguy, pv.higuy, pv.width); } - swap(base, loguy, higuy, width); - } - swap(base, lo, higuy, width); + swap(base, pv.lo, pv.higuy, pv.width); - if ((higuy - 1 - lo) >= (hi - loguy)) { - if (lo + width < higuy) { - lostk[stkptr] = base[lo]; - histk[stkptr] = base[higuy - width]; - ++stkptr; - } + if ((pv.higuy - 1 - pv.lo) >= (pv.hi - pv.loguy)) { + if (pv.lo + pv.width < pv.higuy) { + lostk[stkptr] = pv.lo; + histk[stkptr] = pv.higuy - pv.width; + ++stkptr; + } - if (loguy < hi) { - lo = loguy; - recurse(base, lo, hi, width, n, offset, lostk, histk, stkptr, size); - } - } else { - if (loguy < hi) { - lostk[stkptr] = base[loguy]; - histk[stkptr] = base[hi]; - ++stkptr; - } - if (lo + width < higuy) { - hi = higuy - width; - recurse(base, lo, hi, width, n, offset, lostk, histk, stkptr, size); + if (pv.loguy < pv.hi) { + pv.lo = pv.loguy; + continue; + } + } else { + if (pv.loguy < pv.hi) { + lostk[stkptr] = pv.loguy; + histk[stkptr] = pv.hi; + ++stkptr; + } + if (pv.lo + pv.width < pv.higuy) { + pv.hi = pv.higuy - pv.width; + continue; + } } } - } - --stkptr; - if (stkptr >= 0) { - base[lo] = lostk[stkptr]; - base[hi] = histk[stkptr]; - recurse(base, lo, hi, width, n, offset, lostk, histk, stkptr, size); + --stkptr; + if (stkptr >= 0) { + pv.lo = lostk[stkptr]; + pv.hi = histk[stkptr]; + continue; + } + cont = false; } } @@ -249,6 +254,7 @@ public class Sort { * compareRecord * ============================================================================= */ + public static int cmp(char[] base, int p1, int p2, int n, int offset) { @@ -260,14 +266,41 @@ public class Sort { char u1 = base[s1]; char u2 = base[s2]; if (u1 != u2) { - return (u1 - u2); //TODO check this in java + return (u1 - u2); } + s1++; + s2++; } - return 0; } } +public class ptrVal { + int lo; + int hi; + int width; + int n; + int offset; + int loguy; + int higuy; + int max; + int p; + int mid; + + public ptrVal() { + lo = 0; + hi = 0; + width = 0; + n = 0; + offset = 0; + loguy = 0; + higuy = 0; + max = 0; + p = 0; + mid = 0; + } +} + /* ============================================================================= * * End of sort.java diff --git a/Robust/src/Benchmarks/SingleTM/Bayes/makefile b/Robust/src/Benchmarks/SingleTM/Bayes/makefile index 739fcb32..b26eb88c 100644 --- a/Robust/src/Benchmarks/SingleTM/Bayes/makefile +++ b/Robust/src/Benchmarks/SingleTM/Bayes/makefile @@ -16,7 +16,7 @@ SRC=tmp${MAINCLASS}.java \ tmpIntList.java \ IntListNode.java \ tmpQueue.java \ - ../common/Random.java \ + Random.java \ ../common/Vector_t.java \ ../common/ListNode.java \ ../common/List.java \ -- 2.34.1