Nuova

Nuova is an esoteric programming language defined by the following C implementation:
WARNING: THE "AFTERMATCH" SECTION CONTAINS SPOILERS.
== The language ==
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#define P(a,b) {u32 x=a;x^=x>>17;x*=0xed5ad4bbU;x^=x>>11;x*=0xac4c1b51U;x^=x>>15;x*=0x31848babU;x^=x>>14;b=x;}
typedef uint32_t u32;
u32*mem,s;uint16_t t[16640],ai;void gw(u32 a){if(__builtin_expect(a>=s,0)){u32 i=s;s=a+1;mem=realloc(mem,s*sizeof(u32));while(i>6;t[ai+1]+=(g-t[ai+1])>>6;int w=p&127;ai=(p>>2)+(c<<6)+c;return(t[ai]*(128-w)+t[ai+1]*w)>>15;
}u32 pc(u32 x){x-=(x>>1)&0x55555555;x=(x&0x33333333)+((x>>2)&0x33333333);x=(x+(x>>4))&0x0f0f0f0f;return(x*0x01010101)>>24;}
int main(int argc,char*argv[]) {for(int i=0;i<256;i++)for(int j=0;j<65;j++)t[i*65+j]=i==0?j<<10:t[j];FILE*in=fopen(argv
[1],"rb");u32 idx=0;while(!feof(in)){uint8_t instr=fgetc(in);ms(idx,mg(idx)^instr);idx++;if((instr&15)==15){u32 value=0;
for(int i=0;i<4;i++)value=(value<<8)|fgetc(in);ms(idx,mg(idx)^value);idx++;}}fclose(in);for(u32 i=1;i<idx;i++)ms(idx,mg
(idx)^sse(mg(i-1)&255,mg(i)&255,pc(mg(i))&1));u32 a=0x66,b=0xF0,c=0x0F,ip=0;for(;;){switch(mg(ip++)){
case 0x0F:a=mg(ip++);break; case 0x1F:b=mg(ip++);break;
case 0x2F:c=mg(ip++);break; case 0x3F:ip=mg(ip++);break;
case 0x4F:if(a<=b)ip=mg(ip++);break; case 0x5F:if(b>=c)ip=mg(ip++);break;
case 0x6F:a=sse(b&0xFF,c&0xFF,pc(mg(ip++))&1);break; case 0x00:ms(ip++,a);break;
case 0x10:ms(ip++,b);break; case 0x20:ms(ip++,c);break;
case 0x30:ms(a,b);break; case 0x40:ms(a,c);break;
case 0x50:ms(a,mg(a));break; case 0x60:b=a;break;
case 0x70:c=a;break; case 0x80:a=b;break;
case 0x90:a=c;break; case 0xA0:ip=a;break;
case 0xB0:a=b+c;break; case 0xC0:a=b-c;break;
case 0xD0:putchar(a);break; case 0xE0:a=getchar();break;
case 0xF0:return 0; default:P(a,a);P(b,b);P(c,c);}}}
Nuova has been designed for the Esolang Reverse Engineering Contest. The following tasks were available to be solved using Nuova:
* 1 point: Create a program that prints "Hi" without a linefeed.
* 2 points: Create a program that prints "Hello, World!" with a linefeed.
* 4 points: Make a cat program that does not terminate.
* 6 points: Make a cat program that terminates on EOF.
* 16 points: Make a fizzbuzz program that displays a specified amount of sequence items (as a decimal number, 0-10000).
* 30 points: Prove that the language is Turing-complete (either by creating an interpreter for a TC language in it or compiling a TC language into it). Assume that the registers and memory are unbounded and provide reasoning behind your proof.
The user fireflame241 won the contest with 59 points (max), and 439'939 bytes (the code size being a tiebreaker), their writeup is available on GitHub: .
== Aftermatch ==
A few issues were found with Nuova, e.g. ms(i, sse(...)) was supposed to be ms(idx, sse(...)), which decreased the difficulty of the language (only the first memory cell is affected). Some instructions are implemented incorrectly (and thus do not work) as a result of a hasty programming error. User:Palaiologos (the author) gives the following explanation for the sse function.
sse maps p using a piecewise linear function with 32 segments; each vertex is represented by a pair of 8-bit counters (n0, n1) except that now the counters use a stationary model. when input is p and a 0 or 1 is observed as b, then the corresponding count (n0, n1) of the two vertices on either side of p are incremented. When a count exceeds the maximum of 255, both counts are halved. The output p is a linear interpolation of n1/n between the vertices on either side. the vertices are scaled to be longer in the middle of the graph and short near the ends; the intial counts are set so that p maps to itself, so that it's possible to write programs for nuova in general (or at least so i thought when i wanted to run all the data through sse)