Dieses Dokument ist wie die anderen aus dem Jahre 2012 angefangen und nicht beendet worden.

Folgethema fuer ArrayBuffer ist: "Wie schreibe ich einen eigenen Heap mit Garbage Collector?"

[social buttons]

Binäre Puffer und Typed Arrays

Für die einfachste und unbeliebteste Programmiersprache der Welt

JavaScript für Hartz IV Empfänger [die ersten Zeilen]

MDN logo.js

Motivation

JavaScript ist von Anfang an bekannt dafuer gewesen, keinerlei I/O Routinen, die Lesen und Schreiben von Dateien ermoeglichen, zu haben.

1. Mittlerweile hat sich das geaendert. Seit EcmaScript 5 gibt sogenannte Typed Arrays. Das sind Views, die auf einem ArrayBuffer arbeiten und bestimmten Datentypen in ihrer groesse und ihrem Aufbau entsprechen. Entstanden sind sie zusammen mit dem WebGL Projekt der Khronos Group.

2. In WebGL wird mit Typed Arrays die Graphikkarte gefuettert. Seit HTML5 gibt es ausserdem noch die Moeglichkeiten per XMLHttpRequest, der File API, sowie der WebSocket API an binaere Daten ranzukommen. Auf dem Server, zum Beispiel Node.js gibt es den Buffer.

3. Etwas ueber ein Jahr nach dem Einstieg in JavaScript, habe ich es verstanden: Ich kann damit Heaps definieren. Das heisst einen grossen, dynamischen Speicherbereich, in dem ich allozieren und freen kann und sogar Garbage Collecten.

  1. ArrayBuffer - ein Buffer fuer binaere Daten, den man mit einer groesse Initialisiert und dann verschiedene Views drauf anwenden kann. Es koennen auch mehrere Views (Arrays) ueber die gleichen Bytes lesen (in unterschiedlicher Groesse). Aenderungen werden in den anderen Views sofort sichtbar.
  2. Uint8Array bis Float64Array - Views, die auf einem ArrayBuffer arbeiten. Man kann einen 8Byte Puffer als acht einzelne Bytes sehen, oder als zwei Integer, einen Float64Array mit nur einem Element.
  3. DataView - eine Moeglichkeit den Buffer zu inspizieren und an bestimmten Stellen (offset) bestimmte Typen (xyzArray.BYTES_PER_ELEMENT) zu lesen. Der ist etwas flexibler als ein bestimmter TypedArray

Heap mit Garbage Collector

Der Mark & Sweep GC ist frei nach MIT 6.172 Performance Engineering Lektion 10 in OCW, der Professor erklaert ihn dort muendlich und zeigt Diagramme und hat Pseudocode auf der Folie. BFS durch den Graphen. Objekte sind V, Edges die Ptr. Alles was erreichbar ist, als live markieren. Dann von der From Space in die To Space kopieren. Alten Space mit neuem Pointer markieren, um rekursiv neue Adressen setzen zu koennen. Und To Space zu From Space machen. Resizen des Heaps nicht vergessen.

/*
    Wer Bytecode will muss leiden (ueben).
*/

function Heap (heap_space) {

    var space = heap_space || 2048;
    var from = Space(space);
    var to;

    function Space (space) {
	return {
	    heap: new ArrayBuffer(space),
	    sp: 0,
	    dag: Object.create(null)
	};
    }

    /*
	Ab sofort geht ein Ptr nicht mehr als View direkt,
	sondern muss hinter einem Pointer Record stehen um upgedated 
	werden zu koennen
    */

    function Collect() { // Mark and Sweep frei nach 6.172 Lektion 10
	var v;
	var Q = [];	// dequeue (push und shift)
	var r,e,v,o,p,b,i,j;
	var dag = from.dag;
	var bytes = 0;
	for (e in dag) {
	    r = dag[e];
	    v = r.ptr.view;
	    if (r.mark === 1) {
		Q.push({ mark: 1, ptr: { offset: e, view: v } }); // alter view
		bytes += v.byteLength; // ob ich resizen will
	    }
	}
	
	// ich soll bestimmt +1 nehmen oder +0.75?
	if (bytes > (space / 2)) { 
	    space += Math.floor(space * 2) 
	    space += ((b=space % 8) === 0 ? 0 : 8-b);
	}
	
	to = Space(space);
	
	// umkopieren in den to space und pointer updaten
	i=0, j=Q.length;
	while (i < j) {
	    r = Q[i]; // Billiger als O(n) Q.shift()
	    i += 1; 
    	    p = Store(to, Load(r.ptr)); // neue records fuer to wurden in store erzeugt
	    if (p) {
	        o = r.ptr.offset;
	        q = dag[o].ptr;
	        q.view = p.view; // an alle vorherigen besitzer
		q.offset = p.offset; // die neuen daten per reference type (der record bleibt)
	    }
	}
        // space wechseln
	from.dag = null; 
	delete from;
        from = to;
	to = null;
    }

    /*
	Resize: Loesche den alten View,
	nachdem ein neuer alloziert wurde
    */

    function Resize(view, new_size) {
	"use strict";
	if (view instanceof Uint16Array) {
	} else if (view instanceof Float64Array) {
	}
    }

    /*
        Delete simuliert nur das Markieren fuer den GC
	und setzt den Inhalt des Views auf null.
	Fange erst an.
    */

    function Delete(ptr) {
	from.dag[ptr.offset].mark = 0;
        var view = ptr.view; 
	/*for (var i=0, j=view.length; i < j; i++) {
    	    view[i] = 0;
        }*/
	ptr.view = null;
    }

    function Load(ref) {
	"use strict";
	var data;
	var view = ref.view;
        if (view instanceof Uint16Array) {
	    data = "";
	    for (var i=0, j=view.length; i < j; i++) {
		data += String.fromCharCode(view[i]);
	    }
	    return data;
	} else if (view instanceof Float64Array) {
	    return view[0];
	}
    }

    /*
	Speichern auf der Halde
    */

    function Store(buf, data, size) {
	"use strict";
	var offset, view, bpe;
	// buf kann auch to sein
        var sp = buf.sp;
	var dag = buf.dag;
	var heap = buf.heap;
	var rec;
	
	if (typeof data === "string") {	
	    bpe = Uint16Array.BYTES_PER_ELEMENT;	
	    if (size === undefined) size = data.length;
	    offset = sp + (bpe - (sp % bpe)); // align
	    
	    if ((offset + (size*bpe)) > space) {
		// overflow check 
		Collect();
		// hier kann "buf" eh nur "from" sein
		// "to" hat immer genug platz
		sp = from.sp;
		dag = from.dag;
		heap = from.heap;
	        offset = sp + (bpe - (sp % bpe)); // align again
	    }
	    
	    view = new Uint16Array(heap, offset, size);
	    for (var i=0; i < data.length; i++) {
		view[i] = data.charCodeAt(i);
    	    }
    	    
	} else if (typeof data === "number") {
	    bpe = Float64Array.BYTES_PER_ELEMENT;
	    size = 1;
	    offset = sp + (bpe - (sp % bpe)); // align
	    
	    
	    if ((offset + (size*bpe)) > space) {
		// overflow check 
		Collect();
		// hier kann "buf" eh nur "from" sein
		// "to" hat immer genug platz
		sp = from.sp;
		dag = from.dag;
		heap = from.heap;
	        offset = sp + (bpe - (sp % bpe)); // align again
	    }
	    
	    view = new Float64Array(heap, offset, size);
	    view[0] = data;
	}
	if (view) {
	    buf.sp = offset + view.byteLength - 1;
	    dag[offset] = rec = {
		mark: 1,
		ptr: {
		    offset: offset,
		    view: view	
		}
	    };
	    return rec.ptr;	// distributed kann ich mir hier bereits promises vorstellen (kurz, aber, konnte)
	}
    }

    return {
	get buffer  () {
	    return from.heap;
	},
	get byteLength () {
	    return space;
	},
	get used () {
	    return from.sp;
	},
	store: function (data, size) { return Store(from, data, size); },
	load: function (ptr) { return Load(ptr); },
	resize: function (ptr, size) { return Resize(ptr, size); },
	delete: function (ptr) { return Delete(ptr); },
	gc: function () { return Collect(from); }
    };

}

var heap = Heap(2048);

/*
    die heap.store Funktion gibt Referenzen auf den from_space zurueck 
*/


var string = "Hallo Leute, ich komme aus einem Typed Array.";
var string2 = "Hallo Leute, ich bin an einer anderen Stelle.";


var sp1 = heap.store(string);
var sp2 = heap.store(string2);
var int1 = heap.store(32768); 
var int2 = heap.store(6664337); 
var d1 = heap.store(3.325253); 
var d2 = heap.store(124.27e10); 
var s1 = heap.store(-2352); 
var s2 = heap.store(-3453.3252e2); 

/* 
    Die heap.load Funktion holt das, worauf die Referenz zeigt, zurueck 
*/
console.log("--- Lauf 1");
console.log("used: "+heap.used);
console.log("space: "+heap.byteLength);

console.log(heap.load(sp1));
console.log(heap.load(sp2));
console.log(heap.load(int1));
console.log(heap.load(int2));
console.log(heap.load(d1));
console.log(heap.load(d2));
console.log(heap.load(s1));
console.log(heap.load(s2));


heap.delete(sp1);
heap.delete(sp2);
console.log("Nach Delete die Strings laden");

console.log(heap.load(sp1));
console.log(heap.load(sp2));

heap.gc();


console.log("--- Lauf 2");
console.log("used: "+heap.used);
console.log("space: "+heap.byteLength);

console.log("Nach GC und wechseln des Spaces");
console.log(heap.load(sp1));
console.log(heap.load(sp2));
console.log(heap.load(int1));
console.log(heap.load(int2));
console.log(heap.load(d1));
console.log(heap.load(d2));
console.log(heap.load(s1));
console.log(heap.load(s2));

var str = "Das sind jetzt genug Zeichen um den Heap zu ueberlaufen.";
var p;
for (var i = 0; i < 50; i++) {
    p = heap.store(str);
}

console.log("--- Lauf 3");
console.log("used: "+heap.used);
console.log("space: "+heap.byteLength);

console.log(heap.load(p));
console.log(heap.load(sp1));
console.log(heap.load(sp2));
console.log(heap.load(int1));
console.log(heap.load(int2));
console.log(heap.load(d1));
console.log(heap.load(d2));
console.log(heap.load(s1));
console.log(heap.load(s2));


/*
--- Lauf 1
used: 231
space: 2048
Hallo Leute, ich komme aus einem Typed Array.
Hallo Leute, ich bin an einer anderen Stelle.
32768
6664337
3.325253
1242700000000
-2352
-345332.52
Nach Delete die Strings laden
undefined
undefined
--- Lauf 2
used: 55
space: 2048
Nach GC und wechseln des Spaces
undefined
undefined
32768
6664337
3.325253
1242700000000
-2352
-345332.52
--- Lauf 3
used: 5543
space: 6144
Das sind jetzt genug Zeichen um den Heap zu ueberlaufen.
undefined
undefined
32768
6664337
3.325253
1242700000000
-2352
-345332.52


*/

Heap mit ArrayBuffer

Das war am Vormittag. Von einer Idee vom Abend davor. Wie alignt man die Views?

Der Trick ist das Alignment offset = sp + ( BYTES_PER_ELEMENT - (sp % BYTES_PER_ELEMENT) ), was eine naechstmoegliche Aneinanderreihung ermoeglicht.

/*
    Wer Bytecode will muss leiden (ueben).
*/

var heap = new ArrayBuffer(2048); // 2KB
var string = "Hallo Leute, ich komme aus einem Typed Array.";
var string2 = "Hallo Leute, ich bin an einer anderen Stelle.";
var allocator = { sp: 0 }; // tmp

/*
    Lesen vom Heap
*/

function Load(buf, view) {
    "use strict";
    var data;
    if (view instanceof Int32Array) {
	data = "";
	for (var i=0, j=view.length; i < j; i++) {
	    data += String.fromCharCode(view[i]);
	}
	return data;
    } else if (view instanceof Float64Array) {
	return view[0];
    }
}

/*
    Speichern auf der Halde
*/

function Store(buf, data, size) {
    "use strict";
    var sp = allocator.sp;
    var offset, view;
    if (typeof data === "string") {	
	if (size === undefined) size = data.length;
	offset = sp + (4 - (sp % 4)); // align
	view = new Int32Array(buf, offset, size);
	for (var i=0; i < size; i++) {
	    view[i] = data.charCodeAt(i);
	}
	allocator.sp = offset + view.byteLength - 1;
	return view;
    } else if (typeof data === "number") {
	size = 1;
	offset = sp + (8 - (sp % 8)); // align
	view = new Float64Array(buf, offset, size);
	view[0] = data;
	allocator.sp = offset + view.byteLength - 1;
	return view;
    }
}

/*
    die Store Funktion gibt Referenzen auf den Heap zurueck (tmp den view statt einen ptr-record mit offset und size oder anderer info)
*/

var sp1 = Store(heap, string);
var sp2 = Store(heap, string2);
var int1 = Store(heap, 32768); 
var int2 = Store(heap, 6664337); 
var d1 = Store(heap, 3.325253); 
var d2 = Store(heap, 124.27e10); 
var s1 = Store(heap, -2352); 
var s2 = Store(heap, -3453.3252e2); 

/* 
    Die Load Funktion holt das, worauf die Referenz zeigt, zurueck 
*/

console.log(Load(heap, sp1));
console.log(Load(heap, sp2));
console.log(Load(heap, int1));
console.log(Load(heap, int2));
console.log(Load(heap, d1));
console.log(Load(heap, d2));
console.log(Load(heap, s1));
console.log(Load(heap, s2));

/*
Hallo Leute, ich komme aus einem Typed Array.
Hallo Leute, ich bin an einer anderen Stelle.
32768
6664337
3.325253
1242700000000
-2352
-345332.52
*/

BitFlags mit Int8Array

Ein Byte fuer 8 1-Bit Flags. Ich addiere oder subtrahiere den Wert, der durch 1 << bitstelle erzeugt wird zum Byte.

function BitFlags (byteLen) {
    
    var bits = new Int8Array(byteLen);
    
    function set (n, v) {
	v = +!!v;
	var i = Math.floor(n / 8);
	if (i > byteLen || n < 0) throw new RangeError("Out of Bounds");
	var k = 1 << (n % 8)
	
	console.log("setze "+n+": "+ !!v ); // debug + entferne
	
	if (v) {
	    if (!(bits[i] & k)) bits[i] += k;
	} else {
	    if (bits[i] & k) bits[i] -= k;
	}
    }
    
    function is (n) {
	var i = Math.floor(n/8);
	if (i > byteLen || n < 0) throw new RangeError("Out of Bounds");
	return !!(bits[i] & (1 << (n % 8)));
    }

    var bf = {
	bits: bits,
	set: set,
	is: is
    };

    return bf;
}

/*
var set1 = BitFlags(1);
var set2 = BitFlags(2);

set1.set(1, false);
set1.set(2, false);
set1.set(3, true);
console.log(set1.is(0));
console.log(set1.is(1));
console.log(set1.is(2));
console.log(set1.is(3));

set1.set(1, false);
set1.set(2, true);
set1.set(3, false);
console.log(set1.is(0));
console.log(set1.is(1));
console.log(set1.is(2));
console.log(set1.is(3));

set1.set(1, true);
set1.set(2, true);
set1.set(3, true);
console.log(set1.is(0));
console.log(set1.is(1));
console.log(set1.is(2));
console.log(set1.is(3));

set1.set(1, false);
set1.set(2, false);
set1.set(3, false);
console.log(set1.is(0));
console.log(set1.is(1));
console.log(set1.is(2));
console.log(set1.is(3));

set2.set(7, true);
set2.set(8, true);
set2.set(12, true);
console.log(set2.is(6));
console.log(set2.is(7));
console.log(set2.is(8));
console.log(set2.is(12));

setze 1: false
setze 2: false
setze 3: true
false
false
false
true
setze 1: false
setze 2: true
setze 3: false
false
false
true
false
setze 1: true
setze 2: true
setze 3: true
false
true
true
true
setze 1: false
setze 2: false
setze 3: false
false
false
false
false
setze 7: true
setze 8: true
setze 12: true
false
true
true
true
*/

ArrayBuffer

ArrayBuffers sind binaere Puffer. Anstelle in ECMAScript bekanntes Coercen von Values auf den ArrayBuffer anzuwenden, wird dieser so betrachtet, wie er ist, als binaerer Speicherplatz. Die Views oder TypedArrays sorgen dafuer

	    var ab = new ArrayBuffer(1024 * 1024);
	    
	    // erzeugt einen ArrayBuffer mit 1MB.
	    
	

Typed Arrays

Bytes per Element

Und es gibt den Clamped Array. Er enthaelt Zahlen zwischen 0 und 1.

TypedArray *.BYTES_PER_ELEMENT entspricht in C Beschreibung
Uint8Array 1 unsigned char 8-bit vorzeichenlose Ganzzahl
Uint16Array 2 unsigned short 16-bit vorzeichenlose Ganzzahl
Uint32Array 4 unsigned int 32-bit vorzeichenlose Ganzzahl
Int8Array 1 signed char 8-bit 2er komplementaere vorzeichenbehaftete Ganzzahl
Int16Array 2 signed short 16-bit 2's complement signed integer
Int32Array 4 signed int 32-bit 2's complement signed integer
Float32Array 4 float 32-bit IEEE fp
Float64Array 8 double 64-bit IEEE fp
Uint8ClampedArray 1
	    var ab = new ArrayBuffer(1024*1024);

	    var asfloat64 = new Float64Array(ab, 0, (1024*1024)/Float64Array.BYTES_PER_ELEMENT); // .byteLength = 1048576
	    var asfloat32 = new Float32Array(ab, 0  (1024*1024)/Float32Array.BYTES_PER_ELEMENT); // .byteLength = 1048576 
	    
	    // Achtung. Wer bei node z.B. jetzt asfloat64. und Tab drueckt wird lange warten, weil ueber hunderttausend indizes ausgedruckt werden
	    // wollen
	

Der ArrayBuffer ab hat nun eine Groesse von 1MB. Den man sich wahlweise als asfloat64 oder als asfloat32 angucken kann. So entsprechen asfloat32[0] + asfloat32[1] dem Platz von as64float[0]

DataView

Der DataView ist sozusagen der Rohdiamant der TypedArrays. Mit ihm kann man den Buffer untersuchen und aus ihm Lesen und in ihn Schreiben.

	    var ab = new ArrayBuffer(1024*1024);
	    
	    var dv = new DataView(ab);
	    
	    var i = dv.getInt16(0, true);   // (intByteOffset, boolLittleEndian)
	    
	    dv.setFloat64(4, 2.999999, true); // set->(byteOffset, value, littleEndian);
	    var d = dv.getFloat64(4, true); // get->(intByteOffset, boolLittleEndian);
	    
	    // Achtung. Wer bei node z.B. jetzt dv. und Tab drueckt wird lange warten, weil einige hunderttausend indizes ausgedruckt werden
	    // wollen
	

Der Dataview hat neben den erzeugten Indizes des ArrayBuffers ein paar get und set Methoden, mit denen man den ArrayBuffer manipulieren kann.

getInt8, getIn16, getInt32, getFloat32, getFloat64
setInt8, setUint8, setInt16, setUint16, setInt32, setUint32, setFloat32, setFloat64 Nehmen (byteOffset, value, littleEndian) als Argument. Ausser setInt8 und setUint8, die nur (byteOffset, value) nehmen.

StructType

EcmaScript 6

Die Khronos Gruppe arbeitet eng mit dem TC-39 Kommittee zusammen um einen weiteren View zu kreieren. Mit dem StructType kann man binaere Strukturen erzuegen.

	    /* So sieht ein Vorschlag aus */
	
	    var struct = new StructType({ a: uint16, b: uint32, c: float32 });
	

Anwendung

Binaere Strukturen selbst erzeugen

Angelehnt an die Constructorsyntax vom StructType und dem Verlangen, in JavaScript auch sowas wie struct oder record zu haben, habe ich eine Funktion entwickelt, die es einfach macht, unter Angabe von ein paar Typen, einen ArrayBuffer mit aufeinanderfolgenden Views mit nur einem Befehl und einer Configoption zu erzeugen.

	    /* Source Code */
	    
	    
	    /* Wo ist der denn jetzt hin */
	    
	    
	

Wie das funktioniert? Ich lese das Optionsobjekt aus, in ihm stehen die Definitionen von Typen und Laenge. Diese zaehle ich zusammen, um die Groesse des ArrayBuffers zu erhalten. Ich erzeuge den Buffer von der Groesse, jetzt fahre ich das Optionsobjekt nocheinmal durch und erzeuge entsprechend der angegebenen Typen und Groessen die Views auf dem Array Buffer. Die Namen der Properties nutze ich als Namen der Properties fuer die Arrays.

	    var struct = createBinary({ "eddie": [ "int16", 4 ], "ist": ["float32", 2], "tool": ["uint8", 2 ] });
	    
	    var array = createBinary([ "uint8clamped": 48 ]);
	    
	    struct.eddie[0] = 10;
	    struct.ist[0] = 12;
	    struct.ist[1] = 3.45677575;
	    struct.tool[0] = 4;
	    struct.tool[1] = 5;
	    
	    for (var i = 0, j = array.length; i < j; i++) array[i] = (Math.random()).toPrecision(2);
	
	

Anwendung

Image

Video

Audio

Typed Data

Anwendung

Oggvorbis Information

Den Header eines OggVorbis Musiktitels ausgelesen

MP3 Information

Den ID3 Tag ausgelesen

Anwendung

XMLHttpRequest2

Mit der neuen Version des XMLHttpRequests lassen sich nun auch direkt ArrayBuffer receiven.

	
	var xhr = new XMLHttpRequest();

	xhr.responseType = "arraybuffer";
	
	

Anwendung

Node.js: Buffer

	    // Der Buffer ist im Modul buffer
	
	    var Buffer = require("buffer").Buffer;
	    
	    // Buffer nimmt einen Array mit Bytes an.
	    
	    var buf = new Buffer([0x69,0x70,0x71]);
	    
	    // Die Buffer.prototype.toString Funktion hat einen encoding Parameter
	    
	    console.log(buf.toString("utf8"));
	    
	

Quellen

Typed Arrays, Dataviews und ArrayBuffers haben ihre eigene Spezifikation bei Khronos. Und die ist wiederrum eng verzahnt mit dem JavaScript Standard EcmaScript 5 (und aufwaerts), sowie mit WebGL, der File API, sowie XMLHttpRequest 2, aus der HTML5 Reihe.

Spezifikationen

Hier kann man Interfaces, Properties, Rueckgabewerte, Bezeichner und Funktionsweisen kennenlernen.

Tutorials

Hier kann man praktische Anwendungen ausprobieren.

Bislang habe ich noch keine TypedArray Tutorials gemacht.

Aber..

Ich werde das Dokument im weiteren Verlauf heranziehen und zitieren, weil es genau eins der Themen bereits behandelt, die mit dem Thema einhergehen. Ausserdem haben die mir geholfen.

top