Chapter 21: Instruction Encoding and ELFlinear-chapter21

Co-authored-by:    Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by:    Co-authored-by: godalming123 <68993177+godalming123@users.noreply.github.com>

25 files changed, 406 insertions, 93 deletions

diff --git a/src/test/java/com/seaofnodes/simple/progs/antiDep1.smp b/src/test/java/com/seaofnodes/simple/progs/antiDep1.smp
new file mode 100644
index 00000000..b18dfd16
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/antiDep1.smp
@@ -0,0 +1,11 @@
+// -*- mode: java;  -*-
+struct S { int f; };
+var v0 = new S;
+S? v1;
+if (arg) v1 = new S;
+if (v1) {
+    v0.f = v1.f;
+} else {
+    v0.f = 2;
+}
+return v0;
diff --git a/src/test/java/com/seaofnodes/simple/progs/arg_count.c b/src/test/java/com/seaofnodes/simple/progs/arg_count.c
new file mode 100644
index 00000000..e247e28a
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/arg_count.c
@@ -0,0 +1,10 @@
+#include <stdio.h>
+
+__attribute__ ((CALL_CONV))
+extern double addAll( long long i0, double f1, long long i2, double f3, long long i4, double f5, long long i6, double f7, long long i8, double f9, long long i10, double f11, long long i12, double f13, long long i14, double f15, long long i16, double f17, long long i18, double f19 );
+
+int main() {
+  double result = addAll( 0, 1.1, 2, 3.1, 4, 5.1, 6, 7.1, 8, 9.1, 10, 11.1, 12, 13.1, 14, 15.1, 16, 17.1, 18, 19.1 );
+  printf("%f\n", result);
+  return 0;
+}
diff --git a/src/test/java/com/seaofnodes/simple/progs/arg_count.smp b/src/test/java/com/seaofnodes/simple/progs/arg_count.smp
new file mode 100644
index 00000000..6b6bc0ae
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/arg_count.smp
@@ -0,0 +1,6 @@
+// -*- mode: java;  -*-
+val addAll = { int i0, flt f1, int i2, flt f3, int i4, flt f5, int i6, flt f7, int x8, flt f9, int i10, flt f11, int i12, flt f13, int i14, flt f15, int x16, flt f17 int x18, flt f19 ->
+    return
+    i0 + f1+ i2+ f3+ i4+ f5+ i6+ f7+ x8 +f9 +
+    i10+f11+i12+f13+i14+f15+x16+f17+x18+f19 ;
+};
diff --git a/src/test/java/com/seaofnodes/simple/progs/array1.smp b/src/test/java/com/seaofnodes/simple/progs/array1.smp
new file mode 100644
index 00000000..6b10f92c
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/array1.smp
@@ -0,0 +1,9 @@
+// -*- mode: java;  -*-
+int[] !ary = new int[arg];
+// Fill [0,1,2,3,4,...]
+for( int i=0; i<ary#; i++ )
+    ary[i] = i;
+// Fill [0,1,3,6,10,...]
+for( int i=0; i<ary#-1; i++ )
+    ary[i+1] += ary[i];
+return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6
diff --git a/src/test/java/com/seaofnodes/simple/progs/brain_fuck.c b/src/test/java/com/seaofnodes/simple/progs/brain_fuck.c
new file mode 100644
index 00000000..127cbe73
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/brain_fuck.c
@@ -0,0 +1,18 @@
+#include <stdio.h>
+#include <stdbool.h>
+
+typedef struct AryInt {
+    unsigned int len;
+    unsigned char data[];
+} AryInt;
+
+__attribute__ ((CALL_CONV))
+extern AryInt* brain_fuck();
+
+int main() {
+  AryInt* ps = brain_fuck();
+
+  printf("%.*s", ps->len, ps->data);
+
+  return 0;
+}
diff --git a/src/test/java/com/seaofnodes/simple/progs/brain_fuck.smp b/src/test/java/com/seaofnodes/simple/progs/brain_fuck.smp
new file mode 100644
index 00000000..ed90cb84
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/brain_fuck.smp
@@ -0,0 +1,46 @@
+// -*- mode: java;  -*-
+val brain_fuck = { ->
+    u8[] !program = new u8[106];program[0] = 43;program[1] = 43;program[2] = 43;program[3] = 43;program[4] = 43;program[5] = 43;program[6] = 43;program[7] = 43;program[8] = 91;program[9] = 62;program[10] = 43;program[11] = 43;program[12] = 43;program[13] = 43;program[14] = 91;program[15] = 62;program[16] = 43;program[17] = 43;program[18] = 62;program[19] = 43;program[20] = 43;program[21] = 43;program[22] = 62;program[23] = 43;program[24] = 43;program[25] = 43;program[26] = 62;program[27] = 43;program[28] = 60;program[29] = 60;program[30] = 60;program[31] = 60;program[32] = 45;program[33] = 93;program[34] = 62;program[35] = 43;program[36] = 62;program[37] = 43;program[38] = 62;program[39] = 45;program[40] = 62;program[41] = 62;program[42] = 43;program[43] = 91;program[44] = 60;program[45] = 93;program[46] = 60;program[47] = 45;program[48] = 93;program[49] = 62;program[50] = 62;program[51] = 46;program[52] = 62;program[53] = 45;program[54] = 45;program[55] = 45;program[56] = 46;program[57] = 43;program[58] = 43;program[59] = 43;program[60] = 43;program[61] = 43;program[62] = 43;program[63] = 43;program[64] = 46;program[65] = 46;program[66] = 43;program[67] = 43;program[68] = 43;program[69] = 46;program[70] = 62;program[71] = 62;program[72] = 46;program[73] = 60;program[74] = 45;program[75] = 46;program[76] = 60;program[77] = 46;program[78] = 43;program[79] = 43;program[80] = 43;program[81] = 46;program[82] = 45;program[83] = 45;program[84] = 45;program[85] = 45;program[86] = 45;program[87] = 45;program[88] = 46;program[89] = 45;program[90] = 45;program[91] = 45;program[92] = 45;program[93] = 45;program[94] = 45;program[95] = 45;program[96] = 45;program[97] = 46;program[98] = 62;program[99] = 62;program[100] = 43;program[101] = 46;program[102] = 62;program[103] = 43;program[104] = 43;program[105] = 46;
+    int d = 0;
+    u8[] !output = new u8[0];
+    u8[] !data = new u8[100];
+
+    for( int pc = 0; pc < program#; pc++ ) {
+        var command = program[pc];
+        if (command == 62) {
+            d++;
+        } else if (command == 60) {
+            d--;
+        } else if (command == 43) {
+            data[d]++;
+        } else if (command == 45) {
+            data[d]--;
+        } else if (command == 46) {
+            // Output a byte; increase the output array size
+            var old = output;
+            output = new u8[output# + 1];
+            for( int i = 0; i < old#; i++ )
+                output[i] = old[i];
+            output[old#] = data[d]; // Add the extra byte on the end
+        } else if (command == 44) {
+            data[d] = 42;
+        } else if (command == 91) {
+            if (data[d] == 0) {
+                for( int d = 1; d > 0; ) {
+                    command = program[++pc];
+                    if (command == 91) d++;
+                    if (command == 93) d--;
+                }
+            }
+        } else if (command == 93) {
+            if (data[d]) {
+                for( int d = 1; d > 0; ) {
+                    command = program[--pc];
+                    if (command == 93) d++;
+                    if (command == 91) d--;
+                }
+            }
+        }
+    }
+    return output;
+};
diff --git a/src/test/java/com/seaofnodes/simple/progs/fcn.smp b/src/test/java/com/seaofnodes/simple/progs/fcn.smp
deleted file mode 100644
index 188e0a9f..00000000
--- a/src/test/java/com/seaofnodes/simple/progs/fcn.smp
+++ /dev/null
@@ -1,15 +0,0 @@
-
-struct Person {
-  int age;
-};
-
-val fcn = { Person?[] ps, int x ->
-  val tmp = ps[x];
-  if( ps[x] )
-    ps[x].age++;
-};
-
-Person?[] !ps = new Person?[2];
-ps[0] = new Person;
-ps[1] = new Person;
-fcn(ps,1);
diff --git a/src/test/java/com/seaofnodes/simple/progs/fcn2.smp b/src/test/java/com/seaofnodes/simple/progs/fcn2.smp
deleted file mode 100644
index 049132d9..00000000
--- a/src/test/java/com/seaofnodes/simple/progs/fcn2.smp
+++ /dev/null
@@ -1,5 +0,0 @@
-
-val fcn = (arg&1)
-    ? { int x -> x*x; }
-    : { int x -> x+x; };
-fcn(arg);
diff --git a/src/test/java/com/seaofnodes/simple/progs/fcn3.smp b/src/test/java/com/seaofnodes/simple/progs/fcn3.smp
deleted file mode 100644
index a64564f0..00000000
--- a/src/test/java/com/seaofnodes/simple/progs/fcn3.smp
+++ /dev/null
@@ -1,42 +0,0 @@
-
-//val fact = { int n -> n <= 1 ? 1 : fact(n-1)*n; }
-struct LL { LL? next; int payload; };
-
-
-struct String {
-
-    val _hashCodeString = { ->
-        int hash=0;
-        for( int i=0; i< cs#; i++ )
-            hash = hash*31 + cs[i];
-        if( !hash ) hash = 123456789;
-        return hash;
-    };
-
-    val equals = { String s ->
-        if( self == s ) return true;
-        if( cs# != s.cs# ) return false;
-        for( int i=0; i< #; i++ )
-            if( [i] != s.cs[i] )
-                return false;
-        return true;
-    };
-
-    int _hashCode = hash();
-    u8[] cs;
-};
-
-
-
-val hashCode= { String self ->
-    int hash = self._hashCode
-    ? self._hashCode
-    : self._hashCode = _hashCodeString(self);
-    return hash;
-};
-
-
-String s = new String { cs = new u8[17]; };
-s.cs[0] =  67; // C
-s.cs[1] = 108; // l
-hashCode(s);
diff --git a/src/test/java/com/seaofnodes/simple/progs/fib.c b/src/test/java/com/seaofnodes/simple/progs/fib.c
new file mode 100644
index 00000000..263d2f13
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/fib.c
@@ -0,0 +1,16 @@
+#include <stdio.h>
+#include <stdbool.h>
+
+
+__attribute__ ((CALL_CONV))
+extern int fib(int x);
+
+int main() {
+  printf("[");
+  for (int i = 0; i < 10; i++) {
+    printf("%d", fib(i));
+    if (i < 9) printf(", ");
+  }
+  printf("]");
+  return 0;
+}
\ No newline at end of file
diff --git a/src/test/java/com/seaofnodes/simple/progs/fib.smp b/src/test/java/com/seaofnodes/simple/progs/fib.smp
new file mode 100644
index 00000000..1512541b
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/fib.smp
@@ -0,0 +1,11 @@
+// -*- mode: java;  -*-
+val fib = {int n ->
+    int f1=1;
+    int f2=1;
+    while( n-- > 1 ){
+        int temp = f1+f2;
+        f1=f2;
+        f2=temp;
+    }
+    return f2;
+};
\ No newline at end of file
diff --git a/src/test/java/com/seaofnodes/simple/progs/jig.smp b/src/test/java/com/seaofnodes/simple/progs/jig.smp
new file mode 100644
index 00000000..00c2a161
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/jig.smp
@@ -0,0 +1,9 @@
+// -*- mode: java;  -*-
+struct s0 {
+    i16 v1;
+    u8 v2;
+};
+s0 !l4Hi9BCnsd = new s0;
+if( new s0.v2+arg )
+    while(1) l4Hi9BCnsd=new s0;
+while(new s0.v2+new s0.v1<=0) {}
diff --git a/src/test/java/com/seaofnodes/simple/progs/loop2.c b/src/test/java/com/seaofnodes/simple/progs/loop2.c
new file mode 100644
index 00000000..934f2d89
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/loop2.c
@@ -0,0 +1,7 @@
+
+__attribute__ ((CALL_CONV))
+extern int loop2();
+
+int main() {
+  return loop2();
+}
diff --git a/src/test/java/com/seaofnodes/simple/progs/loop2.smp b/src/test/java/com/seaofnodes/simple/progs/loop2.smp
new file mode 100644
index 00000000..01ec827e
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/loop2.smp
@@ -0,0 +1,10 @@
+// -*- mode: java;  -*-
+int i = 0;
+while(true) {
+    i += 1;
+    if( i==0 ) continue;
+    if( i==1 ) continue;
+    if( i==2 ) break;
+    continue;
+}
+return i;
diff --git a/src/test/java/com/seaofnodes/simple/progs/newtonFloat.c b/src/test/java/com/seaofnodes/simple/progs/newtonFloat.c
new file mode 100644
index 00000000..7e7e796d
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/newtonFloat.c
@@ -0,0 +1,16 @@
+#include <stdio.h>
+#include <math.h>
+#include <stdlib.h>
+
+extern double test_sqrt(double);
+
+int main( int argc, char** argv ) {
+  for( int i=0; i<10; i++ ) {
+    double d = test_sqrt((double)i), expect = sqrt((double)i);
+    double delta = fabs(d-expect);
+    printf("%d  %f   (%g)\n",i,d,delta);
+    if( delta > 1e-15 )
+      return 1;
+  }
+  return 0;
+}
diff --git a/src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp b/src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp
new file mode 100644
index 00000000..be2dffec
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/newtonFloat.smp
@@ -0,0 +1,12 @@
+// -*- mode: java;  -*-
+// Newtons approximation to the square root
+val test_sqrt = { flt x ->
+    flt epsilon = 1e-15;
+    flt guess = x;
+    while( 1 ) {
+        flt next = (x/guess + guess)/2;
+        if( guess-epsilon <= next & next <= guess+epsilon ) return guess;
+        //if( guess==next ) return guess;
+        guess = next;
+    }
+};
diff --git a/src/test/java/com/seaofnodes/simple/progs/no_stack_arg_count.smp b/src/test/java/com/seaofnodes/simple/progs/no_stack_arg_count.smp
new file mode 100644
index 00000000..20a05445
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/no_stack_arg_count.smp
@@ -0,0 +1,6 @@
+// -*- mode: java;  -*-
+val addAll = { int i0, flt f1, int i2, flt f3, int i4, flt f5, int i6, flt f7, int x8, flt f9, int i10, flt f11, int i12, flt f13, int i14, flt f15 ->
+    return
+    i0 + f1+ i2+ f3+ i4+ f5+ i6+ f7+ x8 +f9 +
+    i10+f11+i12+f13+i14+f15;
+};
diff --git a/src/test/java/com/seaofnodes/simple/progs/person.c b/src/test/java/com/seaofnodes/simple/progs/person.c
new file mode 100644
index 00000000..df95e1ca
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/person.c
@@ -0,0 +1,34 @@
+#include <stdio.h>
+#include <stdbool.h>
+#include <stdlib.h>
+
+typedef struct Person {
+    int age;
+} Person;
+
+typedef struct PersonArray {
+    unsigned int length;
+    int pad;
+    Person* data[];
+} PersonArray;
+
+__attribute__ ((CALL_CONV))
+extern void fcn(PersonArray* people, int index);
+
+int main() {
+    Person base[5] = {{25},{1},{18},{45},{60}};
+    unsigned char buf[8+8*5];
+    PersonArray* people_array = (PersonArray*)buf;
+    people_array->length=5;
+    for (int i=0; i<people_array->length; i++) people_array->data[i] = &base[i];
+
+    fcn(people_array, 1);
+    fcn(people_array, 1);
+    fcn(people_array, 1);
+    fcn(people_array, 1);
+    fcn(people_array, 1);
+
+    printf("%d\n", people_array->data[1]->age); // expected: 6
+
+    return 0;
+}
\ No newline at end of file
diff --git a/src/test/java/com/seaofnodes/simple/progs/person.smp b/src/test/java/com/seaofnodes/simple/progs/person.smp
new file mode 100644
index 00000000..9f0f5bea
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/person.smp
@@ -0,0 +1,9 @@
+// -*-java-*-
+struct Person {
+    int age;
+};
+
+val fcn = { Person?[] ps, int x ->
+    if( ps[x] )
+        ps[x].age++;
+};
\ No newline at end of file
diff --git a/src/test/java/com/seaofnodes/simple/progs/sieve.c b/src/test/java/com/seaofnodes/simple/progs/sieve.c
new file mode 100644
index 00000000..cac4cfa3
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/sieve.c
@@ -0,0 +1,19 @@
+#include <stdio.h>
+#include <stdbool.h>
+
+typedef struct AryInt {
+  unsigned int len;
+  unsigned int data[];
+} AryInt;
+
+__attribute__ ((CALL_CONV))
+extern AryInt *sieve(int N);
+
+int main() {
+  AryInt* ps = sieve(100);
+  printf("%d[",ps->len);
+  for( int i=0; i<ps->len; i++ )
+    printf("%d, ",ps->data[i]);
+  printf("]");
+  return 0;
+}
diff --git a/src/test/java/com/seaofnodes/simple/progs/sieve.smp b/src/test/java/com/seaofnodes/simple/progs/sieve.smp
index 0788e6c5..569dbb96 100644
--- a/src/test/java/com/seaofnodes/simple/progs/sieve.smp
+++ b/src/test/java/com/seaofnodes/simple/progs/sieve.smp
@@ -1,32 +1,31 @@
-
-int[] !ary = new int[arg], !primes = new int[arg];
-int nprimes = 0, p=2;
-// Find primes while p^2 < arg
-while( p*p < arg ) {
-    // skip marked non-primes
-    while( ary[p]==1 ) p = p + 1;
-    // p is now a prime
-    primes[nprimes] = p;  nprimes = nprimes + 1;
-    // Mark out the rest non-primes
-    int i = p + p;
-    while( i < ary# ) {
-        ary[i] = 1;
-        i = i + p;
-    }
-    p = p + 1;
-}
-// Now just collect the remaining primes, no more marking
-while( p < arg ) {
-    if( ary[p] == 0 ) {
-        primes[nprimes] = p;  nprimes = nprimes + 1;
+// -*- mode: java;  -*-
+val sieve = { int N ->
+    // The main Sieve array
+    bool[] !ary = new bool[N];
+    // The primes less than N
+    u32[] !primes = new u32[N>>1];
+    // Number of primes so far, searching at index p
+    int nprimes = 0, p=2;
+    // Find primes while p^2 < N
+    while( p*p < N ) {
+        // skip marked non-primes
+        while( ary[p] ) p++;
+        // p is now a prime
+        primes[nprimes++] = p;
+        // Mark out the rest non-primes
+        for( int i = p + p; i < ary#; i+= p )
+            ary[i] = true;
+        p++;
     }
-    p = p + 1;
-}
-// Copy/shrink the result array
-int[] !rez = new int[nprimes];
-int j = 0;
-while( j < nprimes ) {
-    rez[j] = primes[j];
-    j = j + 1;
-}
-return rez;
+
+    // Now just collect the remaining primes, no more marking
+    for( ; p < N; p++ )
+        if( !ary[p] )
+            primes[nprimes++] = p;
+
+    // Copy/shrink the result array
+    u32[] !rez = new u32[nprimes];
+    for( int j=0; j < nprimes; j++ )
+        rez[j] = primes[j];
+    return rez;
+};
diff --git a/src/test/java/com/seaofnodes/simple/progs/sort.c b/src/test/java/com/seaofnodes/simple/progs/sort.c
new file mode 100644
index 00000000..ad76cc7f
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/sort.c
@@ -0,0 +1,28 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+// Test wrapper to call `sort.smp`
+
+typedef struct AryInt {
+    unsigned int len;
+    long long data[];
+} AryInt;
+
+__attribute__ ((CALL_CONV))
+extern AryInt* merge_sort(AryInt*);
+
+
+long long primes[] = { 25, 97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2 };
+
+int main() {
+  AryInt *as = (AryInt*)primes;
+
+  merge_sort(as);
+
+  printf("%d[",as->len);
+  for( int i=0; i<as->len; i++ )
+    printf("%d, ",as->data[i]);
+  printf("]");
+
+  return 0;
+}
\ No newline at end of file
diff --git a/src/test/java/com/seaofnodes/simple/progs/sort.smp b/src/test/java/com/seaofnodes/simple/progs/sort.smp
new file mode 100644
index 00000000..ae3f4f23
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/sort.smp
@@ -0,0 +1,38 @@
+// -*- mode: java;  -*-
+// based on the top-down version from https://en.wikipedia.org/wiki/Merge_sort
+
+val merge_sort = { int[] a ->
+    int[] !b = new int[a#];
+    copy_array (a, 0, a#, b);
+    split_merge(a, 0, a#, b);
+};
+
+val split_merge = { int[] b, int begin, int end, int[] a ->
+    if (end - begin <= 1)
+        return 0;
+    int middle = (end + begin) / 2;
+    split_merge(a, begin, middle, b);
+    split_merge(a, middle, end, b);
+    merge(b, begin, middle, end, a);
+    return 0;
+};
+
+val merge = { int[] b, int begin, int middle, int end, int[] a ->
+    int i = begin, j = middle;
+
+    for (int k = begin; k < end; k++) {
+        // && and ||
+        bool cond = false;
+        if (i < middle) {
+            if (j >= end)          cond = true;
+            else if (a[i] <= a[j]) cond = true;
+        }
+        if (cond) b[k] = a[i++];
+        else      b[k] = a[j++];
+    }
+};
+
+val copy_array = { int[] a, int begin, int end, int[] b ->
+    for (int k = begin; k < end; k++)
+        b[k] = a[k];
+};
diff --git a/src/test/java/com/seaofnodes/simple/progs/stringHash.c b/src/test/java/com/seaofnodes/simple/progs/stringHash.c
new file mode 100644
index 00000000..2c6d0fa9
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/stringHash.c
@@ -0,0 +1,30 @@
+#include <stdio.h>
+#include <stdbool.h>
+
+typedef struct ArrayU8 {
+  unsigned int length;
+  unsigned char data[];
+} ArrayU8;
+typedef struct String {
+  ArrayU8 * cs;
+  long long _hashCode;
+} String;
+
+
+__attribute__ ((CALL_CONV))
+extern bool equals(String*st1, String*st2);
+
+int main() {
+  String test1 = {.cs=(ArrayU8*)"\x04\x00\x00\x00test"};
+  String test2 = {.cs=(ArrayU8*)"\x05\x00\x00\x00test1"};
+
+  if( equals(&test1, &test2) ) {
+    printf("Expected test1 and test2 unequal");
+    return 1;
+  }
+  if( !equals(&test2, &test2) ) {
+    printf("Expected test2 and test2 equal");
+    return 1;
+  }
+  return 0;
+}
diff --git a/src/test/java/com/seaofnodes/simple/progs/stringHash.smp b/src/test/java/com/seaofnodes/simple/progs/stringHash.smp
new file mode 100644
index 00000000..dafa7456
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/progs/stringHash.smp
@@ -0,0 +1,31 @@
+// -*- mode: java;  -*-
+struct String {
+    u8[] cs;
+    int _hashCode;
+};
+
+// Compare two Strings
+val equals = { String self, String s ->
+    if( self == s ) return true;
+    if( self.cs# != s.cs# ) return false;
+    for( int i=0; i< self.cs#; i++ )
+        if( self.cs[i] != s.cs[i] )
+            return false;
+    return true;
+};
+
+// Return the String hashCode (cached, and never 0)
+val hashCode = { String self ->
+    self._hashCode
+    ?  self._hashCode
+    : (self._hashCode = _hashCodeString(self));
+};
+
+val _hashCodeString = { String self ->
+    int hash=0;
+    if( self.cs )
+        for( int i=0; i< self.cs#; i++ )
+            hash = hash*31 + self.cs[i];
+    if( !hash ) hash = 123456789;
+    return hash;
+};