jfrech.com
jblog
table of contents

Snippet #2

2018-09-22, post № 203

programming, #bash

cat /dev/urandom > /dev/null

Interpreting brainfuck in C

2018-09-08, post № 202

brainfuck, C, programming, #interpreter

Esoteric programming languages come in an astonishing magnitude of variety — golfing languages, Turing tarpits, obfuscation languages, one-time joke languages and plenty more. However, among all of them, brainfuck is by far one of the most intriguing to me — an elegant combination of syntactic brevity, apparent lack of functionality and the theorectical might of a Turing machine.
Combined with its seemingly trivially realizable implementation, I have implemented brainfuck in Python 2, a brainfuck flavour in Python 2, and even written an interpreter in DrRacket.
However, like Cristofani writes in their The Epistle to the Implementors, writing a satisfactory brainfuck interpreter is no easy task.
Therefore I have designed another brainfuck command-line interpreter, written in pure C (brainfuck.c).

Key features of this implementation are a large tape size, source code pre-processing — instruction condensing and loop matching —, apt command-line flags and C execution speed.
For further detail on the interpreter’s usage, compile the interpreter (e. g. gcc -O2 brainfuck.c -o brainfuck) and run ./brainfuck -h.

To better demonstrate brainfuck’s true power, I wrote a non-Kolmogorov-complexity program; a palindrome tester.

[ A palindrome tester written in brainfuck. ]
[ Jonathan Frech, 21st of August 2018.      ]
[ Tape layout: (STR ... STR NUL FLG ACC)    ]

,[>,]             read in STR
>+                set FLG to true
<<<[              while STR is of length at least two
 [<]>             go to the first byte
 [[>]>>+<<<[<]>-] transfer first byte to ACC
 >[>]<            go to last byte
 [->>>-<<<]       subtract last byte from ACC
 >>>[             if ACC is not zero
  <[-]            set FLG to false
  >-]             clear ACC
 <[<+>-]          move FLG over
 <<<<             go to last byte
]>>>.             output FLG
% echo ",[>,]>+<<<[[<]>[[>]>>+<<<[<]>-]>[>]<[->>>-<<<]>>>[<[-]>-]<[<+>-]<<<<]>>>.\!existence" > palindrome.b
% ./brainfuck -x palindrome.b
00000000: 00                                       .               

% echo ",[>,]>+<<<[[<]>[[>]>>+<<<[<]>-]>[>]<[->>>-<<<]>>>[<[-]>-]<[<+>-]<<<<]>>>.\!hubbibbuh" > palindrome.b
% ./brainfuck -x palindrome.b
00000000: 01                                       .

Heapsort

2018-08-11, post № 201

C, programming, #algorithms, #sorting

Introduction

Continuing my journey implementing various sorting algorithms in C, in this post I am departing from the most well-known algorithms and implementing one of my personal favourites — heapsort.
Download the C source file here: heapsort.c.

Contrary to algorithms like quicksort which immediately jump into action sorting the given array, heapsort operates on a data structure called a heap which it efficiently transforms into a sorted list. However, as most arrays are not of the heap structure, heapsort first needs to transform a given array into a heap. Thus heapsort is a two-step process — first creating a heap and then sorting said heap.

Sorting can be applied to an infinite number of objects provided there is an order defined among them. However, not much is gained from changing the underlying value one is sorting which is why in this post I will only focus on sorting integers — technically even only integers in the C type sense; n\in\mathbb{Z},-2^{31} \leq n < 2^{31}.

The Heap

A heap is a special type of binary tree that satisfies the heap property — every parent node’s value is not less than its child node’s (if existent) values. Furthermore, a heap is maximally filled at every level but possibly the last where the elements are as far left as possible.
From these properties it follows that the greatest value will be located at the root node.

One can also define a heap such that the root node will house the smallest element; such a heap would lead to a list sorted in descending order (more on that later).

      ( 86 )      
     /      \     
  (31)      (64)  
  /  \      /     
(20)(-4)  (17)    

A heap containing integers.

Snippet #1

2018-07-14, post № 200

mathematics, #analysis, #formal calculation, #symbolic

\nabla=\frac{\Delta}{\nabla}

Tau Day MMXVIII

2018-06-28, post № 199

C, programming,

                                     int
        O=19,I=19;typedef long double f 
    ;long fac(long n){return n?n--*fac( 
  n):1;}f pow(f x,int p){return p--?x   
 *pow(x,p):1;}f sin(f x){f v=0;for      
(int           k=~0;++k                 
<=             O;)k%2&&                 
              (v+=(~-k                  
             %4?-1:1)*                  
             pow(x,k)                   
            /fac(k));                   
            return v                    
           ;}main()                     
           {f a=6,b                     
          =7, tau;                      
          for (int                      
         j=~0;++j                       
         <I;)sin(           tau         
        =a+(b-a)           /2           
        )>0? (b=          tau           
        ):(a=tau        )  ;            
        printf (      "%ca"             
        "u ~ %.*Lf",116,                
           O,tau);}                     

Try it online!

Happy tau day.

Truth

2018-06-16, post № 198

mathematics, programming, Python, #logic, #proposition calculus

Proposition calculus deals with statements and the relation between statements, where each of them can only be in one of two states; \vdash p\lor\lnot p. Therefore, when working with finitely many connected propositions, one can algorithmically determine all possible truth values of all atomic and thus connected propositions.

Truth is command-line tool which was written to precisely perform those computations; computing a logical expression’s truth value. Download link: truth.py
A list of all supportet operators can be seen by invoking the tool with a --help flag.
This project was inspired by Albert Menne’s Einführung in die Logik [1]; the operator syntax used is similar to his, translated to be 7-bit-ASCII-compatible.

Truth can be used to either verify universally true statements, e. g. tertium non datur and a property of the replication, verum sequitur ex quodlibet.

-(p&-p) <-> 1  ,  1 <- p
1 0010   1  1     1 1  0
1 1001   1  1     1 1  1

Though not only absolute truth, but also complete relational equivalence between two expressions can be shown.

(p->q)|(r>-<s) <-> q|(r|s)&-(r&s)|-p
 01 0 1 0 0 0   1  00 000 01 000 110
 10 0 0 0 0 0   1  00 000 01 000 001
 01 1 1 0 0 0   1  11 000 01 000 110
 11 1 1 0 0 0   1  11 000 01 000 101
 01 0 1 1 1 0   1  01 110 11 100 110
 10 0 1 1 1 0   1  01 110 11 100 101
 01 1 1 1 1 0   1  11 110 11 100 110
 11 1 1 1 1 0   1  11 110 11 100 101
 01 0 1 0 1 1   1  01 011 11 001 110
 10 0 1 0 1 1   1  01 011 11 001 101
 01 1 1 0 1 1   1  11 011 11 001 110
 11 1 1 0 1 1   1  11 011 11 001 101
 01 0 1 1 0 1   1  00 111 00 111 110
 10 0 0 1 0 1   1  00 111 00 111 001
 01 1 1 1 0 1   1  11 111 00 111 110
 11 1 1 1 0 1   1  11 111 00 111 101

Complete contravalence can also be shown.

-(p/-p>-<0)|p->q<-r >-< p&-q&r
0 0110 1 0 101 01 0  1  001000
0 1101 1 0 110 01 0  1  111000
0 0110 1 0 101 11 0  1  000100
0 1101 1 0 111 11 0  1  100100
0 0110 1 0 101 01 1  1  001001
0 1101 1 0 010 00 1  1  111011
0 0110 1 0 101 11 1  1  000101
0 1101 1 0 111 11 1  1  100101

Worldwide Pinhole Day MMXVIII

2018-05-19, post № 197

art, #analogue, #photography, #pinhole photography, #WWPD

On the last sunday in April of 2018, the 29th, to commemorate Worldwide Pinhole Day, I ventured out in the wilderness to capture a few photons.

worldwide-pinhole-day-mmxviii-09.png
worldwide-pinhole-day-mmxviii-08.png
worldwide-pinhole-day-mmxviii-06.png

Snippet #0

2018-05-12, post № 196

JavaScript, programming, #lambda function

(_=>_<=_)([]>{})

Lichen, Extraterrestrials, Diodes #0

2018-04-21, post № 195

art, #LED, #photography

lichen-extraterrestrials-diodes-0.jpg

Third Anniversary

2018-03-28, post № 194

, #2017, #collage

Today marks this blog’s third anniversary. To celebrate and take a look back at the year, I have collected a few image highlights.

17500615947440398742637684298448259300459653195179624088723406481656498345927782897306957959023081425157582777952426879442535942327333206022815634243070984075006080698433225695442819778347008.0

BMP Implementation in C — Graphic Primitives

2018-03-24, post № 193

C, programming, #2017, #bitmap, #bmp, #drawing, #image library, #image manipulation, #library

Continuing development of my C bitmap library, I added basic graphic primitives to augment the library’s functionality beyond simply reading and writing bitmaps and manually manipulating individual pixels. Source code can be seen below and also downloaded — bmp.c.
The underlying implementation of the bitmap file format can be seen in my prior post BMP Implementation in C.Graphic primitives include drawing lines, rectangles, circles, ellipses; rotating, flipping, cropping, resizing and blitting images. A full list of defined graphic primitives can be seen below, together with a short functionality description.

bmp-implementation-in-c-graphic-primitives_drw.png
Test image regarding drawing primitives.
/* === DRAWING PRIMITIVES === */
void hline      (image *img, int x0, int x1, int y , int c               ); // draw horizontal line
void vline      (image *img, int x , int y0, int y1, int c               ); // draw vertical line
void line       (image *img, int x0, int y0, int x1, int y1, int c       ); // draw line
void fillrect   (image *img, int x0, int y0, int x1, int y1, int c       ); // draw filled rectangle
void rect       (image *img, int x0, int y0, int x1, int y1, int c       ); // draw rectangle
void fillcircle (image *img, int x , int y , int r , int c               ); // draw filled circle
void circle     (image *img, int x , int y , int r , int t , int c       ); // draw circle (with certain thickness)
void fillellipse(image *img, int x , int y , int rx, int ry, int c       ); // draw filled ellipse
void ellipse    (image *img, int x , int y , int rx, int ry, int t, int c); // draw ellipse (with certain thickness)

/* === TRANSFORMATION PRIMITIVES === */
image *resize   (image *img, int w , int h                                ); // resize an image
image *hflip    (image *img                                               ); // flip horizontally
image *vflip    (image *img                                               ); // flip vertically
image *rrotate  (image *img                                               ); // rotate clockwise
image *lrotate  (image *img                                               ); // rotate counter-clockwise
image *hrotate  (image *img                                               ); // rotate half a revolution
image *crop     (image *img, int x0, int y0, int x1, int y1               ); // crop an image
void   blit     (image *img, image*, int x , int y                        ); // blit an image onto another one
bmp-implementation-in-c-graphic-primitives_flp.png
Test image regarding transformation primitives.

Future plans for this library include performance optimizations regarding the ellipse drawing primitives; circle drawing is already optimized as it uses the shape’s symmetry to save computational cost.Further primitives that may be added include a flood filling functionality as well as the ability to draw irregular polygons.

Source code: bmp.c