simple hashmap in c

So, nochmal ein kleiner Quellcode Formatierungstest in Form einer einfachen hashmap Implementierung in C

  • hashmap.h
  • hashmap.c
  • ut_main.c

Anwendung:

/// Map anlegen:
hashmap map;

/// Map initialisieren:
hashmap_init( &map );

/// Map verwenden:
hashmap_set( &map, "tach", "Hallo Welt", 0 );
printf( "tach:%s\n", hashmap_get( "tach" ) );

/// Map freigeben:
hashmap_free( &map );

hashmap.h

#ifndef HASHMAP_H_INCLUDED
#define HASHMAP_H_INCLUDED

#include <stdint.h>
#include <stddef.h>

#define HASHMAP_NULL_INDEX 0xFFFFFFFF

/**
 *  \brief hashmap key compare function definition
 */
typedef int (*hashmap_compare)(const void *a, const void *b);

/**
 * \brief hashmap key -> hash function definition
 */
typedef uint32_t (*hashmap_hash)(const void *key);

/**
 * \brief hashmap collision solver
 */
typedef uint32_t (*hashmap_collision_solver)( uint32_t index );

/**
 * \brief hashmap malloc
 */
typedef void* (*hashmap_data_malloc)(size_t size);

/**
 * \brief hashmap free
 */
typedef void (*hashmap_data_free)(void*ptr);

/**
 * \brief hashmap key,value pair
 */
typedef struct hashmap_key_value_pair {
    const void* key;                    /**< key */
    uint32_t    bytes_allocated;        /**< data memory allocation size or 0 if only the ptr is copied*/
    void*       value;                  /**< data pointer */
} hashmap_key_value_pair;

/**
 * \brief hashmap struct contains all necessary information for an hashmap
 */
typedef struct hashmap {
    uint32_t    collision_count;        /**< collision counter statistics */
    uint32_t    get_count;              /**< get counter statistics */
    uint32_t    collision_retries;      /**< collsion retries till failure */
    uint32_t    key_value_pair_count;   /**< key value pair list count */

    hashmap_key_value_pair*     key_value_pairs;        /**< key value pair list */

    hashmap_compare             compare_fun;            /**< key compare function (strcmp)*/
    hashmap_hash                hash_fun;               /**< key->hash function (Simple Bob Jenkins's hash algorithm) */
    hashmap_collision_solver    collision_solver_fun;   /**< collsision solver function (index+1)*/
    hashmap_data_malloc         data_malloc_fun;        /**< data memory allocator function (malloc) */
    hashmap_data_free           data_free_fun;          /**< data memory deallocator function (free) */
} hashmap;

/**
 * \brief initialize hashmap if ref_hashmap is NULL a new hashmap is allocated
 * \param ref_hashmap
 * \param size key value pair list size
 * \return initialized hashmap
 */
hashmap*
hashmap_init( hashmap* ref_hashmap, uint32_t size );

/**
 * \brief frees the internal allocated data blocks
 * \param ref_hashmap
 */
void
hashmap_free( hashmap* ref_hashmap );

/**
 * \brief set key, value pair
 * \param ref_hashmap
 * \param key any non NULL value that could by processed by hashmap_compare and hashmap_hash
 * \param data pointer
 * \param copy_bytes greater than 0 -> *data will be copied into an newly allocated block otherwise only the pointer will be duplicated
 */
void
hashmap_set( hashmap* ref_hashmap, const void *key, void *data, uint32_t copy_bytes );

/**
 * \brief get value or NULL if not found
 * \param ref_hashmap
 * \param key any non NULL value that could by processed by hashmap_compare and hashmap_hash
 */
void*
hashmap_get( hashmap* ref_hashmap, const void *key );

/**
 * \brief remove value with the specified key from ref_hashmap
 * \param ref_hashmap
 * \param key any non NULL value that could by processed by hashmap_compare and hashmap_hash
 */
void
hashmap_remove( hashmap* ref_hashmap, const void *key );

/**
 * \brief remove and free all key value pairs allocated
 * \param ref_hashmap
 */
void
hashmap_clear( hashmap* ref_hashmap );

/**
 * \brief print debug information
 * \param ref_hashmap
 */
void
hashmap_debug( const hashmap* ref_hashmap );

/**
 * \brief get internal index from key, use with ref_hashmap->key_value_pairs[ index ]
 * \param ref_hashmap
 * \param key  any non NULL value that could by processed by hashmap_compare and hashmap_hash
 * \return map index or HASHMAP_NULL_INDEX if no suitable slot is found
 */
uint32_t
hashmap_get_index( hashmap* ref_hashmap, const void *key );

#endif // HASHMAP_H_INCLUDED

hashmap.c

#include "hashmap.h"
#include <malloc.h>
#include <stdio.h>
#include <assert.h>
#include <string.h>

/**
 * \brief default comperator : use strcmp
 * \param a
 * \param b
 * \return
 */
int
default_compare(const void *a, const void *b) {
    return strcmp((const char*)a, (const char*)b);
}

/**
 * \brief Simple Bob Jenkins's hash algorithm taken from the wikipedia description
 * \param a
 * \return 32bit hash value
 */
uint32_t
default_hash(const void *a) {
    const uint8_t *key = (const uint8_t *)a;
    uint32_t hash = 0;
    uint32_t i = 0;

    for(hash = i = 0; key[i]; ++i) {
        hash += key[i];
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }

    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);

    return hash;
}

/**
 * \brief Simple collision solver
 * \param index
 * \return next index
 */
uint32_t
default_collision_solver( uint32_t index ) {
    /// simple increment as collision solver
    return index+1;
}

hashmap*
hashmap_init( hashmap* ref_hashmap, uint32_t size ) {
    /// allocate ref_hashmap if necessary
    if( ref_hashmap==NULL )
        ref_hashmap = (hashmap*)malloc( sizeof(hashmap) );
    assert(ref_hashmap);

    /// init key,value list
    ref_hashmap->key_value_pair_count = size;
    ref_hashmap->key_value_pairs = (hashmap_key_value_pair*) malloc( sizeof(hashmap) * ref_hashmap->key_value_pair_count );
    memset( ref_hashmap->key_value_pairs, 0, sizeof(hashmap) * ref_hashmap->key_value_pair_count );

    /// collision retries 10%
    ref_hashmap->collision_retries = size/10;

    /// reset statistics
    ref_hashmap->collision_count=0;
    ref_hashmap->get_count = 0;

    /// set default string comperator
    ref_hashmap->compare_fun = default_compare;

    /// set default string hashing
    ref_hashmap->hash_fun = default_hash;

    /// set default collsion solver
    ref_hashmap->collision_solver_fun = default_collision_solver;

    // set default data memory allcoator / deallocator
    ref_hashmap->data_malloc_fun = malloc;
    ref_hashmap->data_free_fun = free;

    return ref_hashmap;
}

void
hashmap_free( hashmap* ref_hashmap ) {
    assert(ref_hashmap);

    if( ref_hashmap->key_value_pairs ) {
        /// remove and free all allocated data blocks
        hashmap_clear( ref_hashmap );

        /// free memory block for key value pair list
        free( ref_hashmap->key_value_pairs );
        ref_hashmap->key_value_pairs = NULL;
        ref_hashmap->key_value_pair_count = 0;
    }
}

void
hashmap_clear( hashmap* ref_hashmap ) {
    assert(ref_hashmap);
    if( ref_hashmap->key_value_pairs ) {
        uint32_t count = ref_hashmap->key_value_pair_count;
        uint32_t index;

        /// free allocated data blocks
        for( index=0; index<count; ++index) {
            if( ref_hashmap->key_value_pairs[index].bytes_allocated>0 ) {
                ref_hashmap->data_free_fun( ref_hashmap->key_value_pairs[index].value );
                ref_hashmap->key_value_pairs[index].bytes_allocated = 0;
            }
            ref_hashmap->key_value_pairs[index].key = NULL;
            ref_hashmap->key_value_pairs[index].value = NULL;
        }
    }
}

uint32_t
hashmap_get_index( hashmap* ref_hashmap, const void *key ) {
    assert(ref_hashmap);
    assert(key);
    uint32_t count = ref_hashmap->key_value_pair_count;
    uint32_t index = ref_hashmap->hash_fun( key ) % count;
    uint32_t t;

    /// find free slot
    for( t=0; t<ref_hashmap->collision_retries; ++t) {
        if( ref_hashmap->key_value_pairs[index].key==NULL ||
            ref_hashmap->compare_fun( ref_hashmap->key_value_pairs[index].key, key )==0 ) {
            // found!
            ++ref_hashmap->get_count;
            return index;
        }

        /// count collision
        ++ref_hashmap->collision_count;

        /// next index distribution function
        index = ref_hashmap->collision_solver_fun( index ) % count;
    }
    return HASHMAP_NULL_INDEX;
}

void
hashmap_set( hashmap* ref_hashmap, const void *key, void *data, uint32_t copy_bytes ) {
    assert(ref_hashmap);
    assert(key);
    uint32_t index = hashmap_get_index( ref_hashmap, key );
    assert( index<ref_hashmap->key_value_pair_count );

    /// clean previous value
    if( ref_hashmap->key_value_pairs[index].bytes_allocated>0 ) {
        ref_hashmap->data_free_fun( ref_hashmap->key_value_pairs[index].value );
        ref_hashmap->key_value_pairs[index].bytes_allocated = 0;
    }

    /// set value
    ref_hashmap->key_value_pairs[index].key = key;
    if( copy_bytes>0 ) {
        /// allocate data
        ref_hashmap->key_value_pairs[index].bytes_allocated = copy_bytes;
        ref_hashmap->key_value_pairs[index].value = ref_hashmap->data_malloc_fun( copy_bytes );
        assert(ref_hashmap->key_value_pairs[index].value );

        /// copy data
        memcpy(ref_hashmap->key_value_pairs[index].value,data,copy_bytes );
    }
    else {
        /// copy pointer only
        ref_hashmap->key_value_pairs[index].value = data;
    }
}

void*
hashmap_get( hashmap* ref_hashmap, const void *key ) {
    assert(ref_hashmap);
    assert(key);
    uint32_t index = hashmap_get_index( ref_hashmap, key );
    assert( index<ref_hashmap->key_value_pair_count );

    /// return value pointer
    return ref_hashmap->key_value_pairs[index].value;
}

void
hashmap_remove( hashmap* ref_hashmap, const void *key ) {
    assert(ref_hashmap);
    assert(key);
    uint32_t index = hashmap_get_index( ref_hashmap, key );
    assert( index<ref_hashmap->key_value_pair_count );

    if( ref_hashmap->key_value_pairs[index].bytes_allocated>0 ) {
        /// free data block
        free( ref_hashmap->key_value_pairs[index].value );
        ref_hashmap->key_value_pairs[index].bytes_allocated = 0;
    }

    /// remove
    ref_hashmap->key_value_pairs[index].key = NULL;
    ref_hashmap->key_value_pairs[index].value = NULL;
}

void
hashmap_debug( const hashmap* ref_hashmap ) {
    assert(ref_hashmap);
    uint32_t t;
    printf("hashmap_debug(%p) ***START***\n", ref_hashmap);
    printf(" size:=%u\n get_count:=%u\n collision_count:=%u\n",
                                                    ref_hashmap->key_value_pair_count,
                                                    ref_hashmap->get_count,
                                                    ref_hashmap->collision_count
                                                );
    for( t=0;t<ref_hashmap->key_value_pair_count;++t ) {
        if( ref_hashmap->key_value_pairs[t].key )
            printf(" - %4u %p %p(%u) <%s>:=<%s>\n", t,
                   ref_hashmap->key_value_pairs[t].key, ref_hashmap->key_value_pairs[t].value, ref_hashmap->key_value_pairs[t].bytes_allocated,
                   (char*)ref_hashmap->key_value_pairs[t].key, (char*)ref_hashmap->key_value_pairs[t].value );
    }
    printf("hashmap_debug(%p) ***STOP***\n",ref_hashmap );
}

Ein pseudo Unit Test 😉
ut_main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "hashmap.h"

/**
 * \brief unit test unification helper macro
 * \param function
 */
#define TEST( function ) { printf(" [--] " #function "\r" ); if( function()==0 ) puts(" [OK] " #function ); else puts(" [!!] " #function  ); }

/// test data
#define TEST_MAP_SIZE 32
hashmap map;

/**
 * \brief test hashmap init functionality
 * \return test status
 *
 */
int
ut_hashmap_init() {
    hashmap_init( &map, TEST_MAP_SIZE );
    return map.key_value_pair_count==TEST_MAP_SIZE && map.key_value_pairs!=NULL ? 0 : -1;
}

/**
 * \brief test hashmap set and get functionality
 * \return test status
 *
 */
int
ut_hashmap_set_get() {

    /// set test values
    hashmap_set( &map,"first_name", "Thomas", strlen("Thomas")+1 );
    hashmap_set( &map,"last_name", "Mueller", strlen("Mueller")+1 );
    hashmap_set( &map,"age", "25", strlen("25")+1 );

    /// fetch test values
    if( strcmp("Thomas", (char*)hashmap_get(&map,"first_name") ) )
        return -1;

    if( strcmp("Mueller", (char*)hashmap_get(&map,"last_name") ) )
        return -1;

    if( strcmp("25", (char*)hashmap_get(&map,"age") ) )
        return -1;

    return 0;
}

/**
 * \brief test hashmap remove functionality
 * \return test status
 */
int
ut_hashmap_remove() {

    /// remove one entry
    hashmap_remove( &map,"age" );

    if( hashmap_get(&map,"age")!=NULL )
        return -1;

    return 0;
}

/**
 * \brief test hashmap clear functionality
 * \return test status
 */
int
ut_hashmap_clear() {
    uint32_t index;

    /// remove one entry
    hashmap_clear( &map );

    /// test all entries
    for( index=0; index<map.key_value_pair_count; ++index ) {
        if( map.key_value_pairs[index].key!=NULL )
            return -1;
    }

    return map.key_value_pair_count==TEST_MAP_SIZE && map.key_value_pairs!=NULL ? 0 : -1;
}

/**
 * \brief test hashmap free functionality
 * \return test status
 */
int
ut_hashmap_free() {
    /// remove one entry
    hashmap_free( &map );

    /// test internal data
    return map.key_value_pair_count==0 && map.key_value_pairs==NULL ? 0 : -1;
}

/**
*   \brief unit test main function- executes all test functions
*   \return exit code
*/
int main() {
    printf("UnitTest hashmap ***START***\n");

    TEST( ut_hashmap_init );
    TEST( ut_hashmap_set_get );
    TEST( ut_hashmap_remove );
    TEST( ut_hashmap_clear );
    TEST( ut_hashmap_free );

    printf("UnitTest hashmap ***DONE***\n");
    return 0;
}

Reguläre Ausdrücke in C (cregex)

Hier endlich mal wieder ein Blogpost von mir – diesmal wollte ich mein Verständnis für Reguläre Ausdrücke verbessern und kam so auf die Idee eine rudimentäre regex Bibliothek in C zu implementieren.

Idee

Grundlegende Idee der Implementierung ist ein Nicht Deterministischer endlicher Automat (NFA) welcher über eine zweifach verkettete Liste von “states” realisiert wird.
{state->(next,child)}.

Über “next” wird eine Liste parallel zu verarbeitender “states” realisiert. Sobald ein “state” zutrifft werden dessen “child-states” der Verarbeitungsqueue (proc_queue) hinzugefügt.

Ablauf

1. Zuerst werden nun die Startzustände der “proc_queue” hinzugefügt.
2. Jedes Element der “proc_queue” wird nun verarbeitet indem seine “child-states” mit dem aktuellen Eingabestrom entsprechend ihres “commands” verglichen werden. Trifft eines oder mehrere davon zu  werden diese der “proc_queue” hinzugefügt.
3. Jeder “Stop-State” signalisiert nun ein mögliches Ergebnis.

Implementierung

Unterstützt werden momentan folgende Operatoren:
^ \ + . ? * [ ^ ] \w \d \s \W \D \S ( ) $

| (oder) funktioniert scheinbar – es fehlt aber noch die Zusammenführung aller Pfade in ein “sigma_or
(müsste zu jeder Gruppe “(…)” angelegt werden )
p{min,max} ist nur angedacht – es fehlt dafür eine p_in/p_out Unterscheidung von p

Dateien
  cregex.h
  state.h
  state_heap.h
  state_vector_queue.h
  cregex.c
  state_heap.c
  state_vector_queue.c

Anwendung
Zuerst wird ein gegebener Regulärer Ausdruck in ein Status Netzwerk umgewandelt und in der “cregex” Struktur  abgelegt.
    cregex c;
    cregex__compile( &c, “abc+” );

danach kann ein Text mit diesem Netzwerk geprüft werden:
    int result = cregex__match( &c, “abccccc” );

Die Verarbeitung erfolgt mittels eines kleinen Automaten welche den Eingabestrom mittels des Netzwerkes abarbeitet.
cregex_find_next( &c )

Diverse Status Netzwerke

p := previous := vorheriger Status
c := char := zeichen
σ := nächster Status

in := Eingang
next:= der nächste zu verarbeitende Status in der aktuellen Liste
child := der erste zu vergleichende Status in der Liste der “Kinder”



Vergleich eines Zeichens c

Implementierung von ?

Implementierung von *

Implementierung von [c1-cn]

Implementierung von +

Anmerkung:
Quellcode Formatierung für ein Blog ist echt grausam… es kann sein das hier und da mal ein < oder > fehlt- nicht das diese Symbole in C irgendwie von Relevanz wären… 

state.h

#ifndef STATE_H
#define STATE_H
/**
* @brief The state_command enum
*/
typedef enum {
STATE_COMMAND_CHAR = 0, // (+ char value) process if equal
STATE_COMMAND_NOT_CHAR = 10000, // (+ char value) process if not equal
STATE_COMMAND_LINK = 1000, // process child unconditionally
STATE_COMMAND_PUSH_GROUP = 1001,
STATE_COMMAND_POP_GROUP = 1002,
STATE_COMMAND_ANY = 1000+'.',
STATE_COMMAND_NUMBER = 1000+'d',
STATE_COMMAND_WORD = 1000+'w',
STATE_COMMAND_WHITESPACE = 1000+'s',
STATE_COMMAND_NOT_NUMBER = 1000+'D',
STATE_COMMAND_NOT_WORD = 1000+'W',
STATE_COMMAND_NOT_WHITESPACE =1000+'S',
STATE_COMMAND_BEGIN = 1000+'$',
STATE_COMMAND_END = 1000+'^'
} state_command;
/**
* @brief The state struct
*/
struct state {
/**
* @brief command
* match command
*/
int command;
/**
* @brief next
* next state to match
*/
int next;
/**
* @brief child
* following state if match
*/
int child;
};
/**
* @brief The state_vector struct
*/
struct state_vector {
/**
* @brief state
*/
int state;
/**
* @brief text iterator (position)
*/
int it;
};
#endif // STATE_H

state_heap.h

#ifndef STATE_HEAP_H
#define STATE_HEAP_H
#include "state.h"
/**
* @brief The state_heap struct
*/
struct state_heap {
/**
* @brief buffer
*/
struct state* buffer;
/**
* @brief count
*/
int count;
/**
* @brief capacity
*/
int capacity;
};
/**
* @brief state_heap__init
* @param heap
* @param max
* @return state_heap
*/
struct state_heap*
state_heap__init( struct state_heap *heap, int capacity );
/**
* @brief state_heap__free
* @param heap
*/
void
state_heap__free( struct state_heap *heap );
/**
* @brief state_heap__new
* @param heap
* @return heap->buffer index
*/
int
state_heap__new( struct state_heap *heap, int command );
/**
* @brief state_heap__append
* @param heap
* @param list_index
*/
void
state_heap__append( struct state_heap *heap, int list_index, int index );
#endif // STATE_HEAP_H

state_vector_queue.h

#ifndef STATE_VECTOR_QUEUE_H
#define STATE_VECTOR_QUEUE_H
/**
 * predeclaration
 */
struct state;
struct state_vector;
/**
 * @brief The state_heap struct
 */
struct state_vector_queue {
    /**
     * @brief buffer
     */
    struct state_vector* buffer;
    /**
     * @brief write_pos
     */
    int write_pos;
    /**
     * @brief read_pos
     */
    int read_pos;
    /**
     * @brief capacity
     */
    int capacity;
};
/**
 * @brief state_vector_queue__init
 * @param queue
 * @param max
 * @return queue
 */
struct state_vector_queue*
state_vector_queue__init( struct state_vector_queue *queue, int capacity );
/**
 * @brief state_vector_queue__free
 * @param queue
 */
void
state_vector_queue__free( struct state_vector_queue *queue );
/**
 * @brief state_vector_queue__is_empty
 * @param queue
 * @return 1 if empty otherwise 0
 */
int
state_vector_queue__is_empty( struct state_vector_queue *queue );
/**
 * @brief state_vector_queue__enqueue
 * @param queue
 * @param state
 * @param it
 * @return new state_vector
 */
struct state_vector*
state_vector_queue__enqueue( struct state_vector_queue *queue, int state, int it );
/**
 * @brief state_vector_queue__dequeue
 * @param queue
 * @return state_vector (!invalidates after next enqueue call!)
 */
struct state_vector*
state_vector_queue__dequeue( struct state_vector_queue *queue );
#endif // STATE_VECTOR_QUEUE_H

cregex.h

#ifndef CREGEX_H
#define CREGEX_H
#include "state.h"
#include "state_heap.h"
#include "state_vector_queue.h"
/**
* @brief The cregex struct
*/
struct cregex {
/**
* @brief heap
*/
struct state_heap heap;
/**
* @brief proc_queue
*/
struct state_vector_queue proc_queue;
/**
* @brief start_state
*/
int start_state;
/**
* @brief pattern
*/
const char* pattern;
/**
* @brief text
*/
const char* text;
/**
* @brief start_it
*/
int start_it;
/**
* @brief stop_it
*/
int stop_it;
/**
* @brief it
*/
int it;
/**
* @brief length
*/
int length;
};
/**
* @brief cregex__compile
* @param cregex
* @param pattern
* @return
*/
struct cregex*
cregex__compile( struct cregex *cregex, const char *pattern );
/**
* @brief cregex__free
* @param cregex
*/
void
cregex__free( struct cregex *cregex );
/**
* @brief cregex__reset
* @param cregex
*/
void
cregex__reset( struct cregex *cregex );
/**
* @brief cregex__match
* @param cregex
* @param text
* @return
*/
int
cregex__match( struct cregex *cregex, const char *text );
/**
* @brief cregex__find_next
* @param cregex
* @return
*/
int
cregex__find_next( struct cregex *cregex );
/**
* @brief cregex__debug
* @param cregex
*/
void
cregex__debug( struct cregex *cregex );
#endif // CREGEX_H

state_heap.c

// state_heap.c
#include "state_heap.h"
#include "state.h"
#include
#include
/**
* Bufferpage exponent ( exp(2,n) )
* 10 => 1024
*/
#define STATE_HEAP_BUFFER_PAGE_EXP 10
/**
* @brief state_heap__init
* @param heap
* @param max
* @return
*/
struct state_heap* state_heap__init( struct state_heap *heap, int capacity ) {
assert(heap);
heap->buffer = (struct state*)malloc( capacity*sizeof(struct state) );
heap->capacity = capacity;
heap->count = 0;
return heap;
}
/**
* @brief state_heap__free
* @param heap
*/
void
state_heap__free( struct state_heap *heap ) {
assert( heap );
assert( heap->buffer!=NULL );
free( heap->buffer );
heap->buffer=NULL;
heap->capacity=0;
heap->count=0;
}
/**
* @brief state_heap__new
* @param heap
* @return index
*/
int
state_heap__new(struct state_heap *heap, int command) {
assert( heap );
assert( heap->buffer );
// realloc
if( heap->count >= heap->capacity ) {
int new_capacity = ((heap->count>>STATE_HEAP_BUFFER_PAGE_EXP)+1)<<STATE_HEAP_BUFFER_PAGE_EXP;
heap->buffer = (struct state*)realloc( heap->buffer, new_capacity*sizeof(struct state) );
assert( heap->buffer );
heap->capacity = new_capacity;
}
// return new state
heap->buffer[heap->count].child =-1;
heap->buffer[heap->count].next =-1;
heap->buffer[heap->count].command =command;
return heap->count++;
}
/**
* @brief state_heap__append
* @param heap
* @param list_index
*/
void
state_heap__append( struct state_heap *heap, int list_index, int index ) {
assert( heap );
assert( heap->buffer );
assert( list_index!=-1 );
// find tail
for( ;heap->buffer[list_index].next!=-1; list_index=heap->buffer[list_index].next );
// append index
heap->buffer[list_index].next = index;
}

state_vector_queue.c

// state_vector_queue.c
#include "state_vector_queue.h"
#include "state.h"
#include
#include
#include
/**
* Bufferpage exponent ( exp(2,n) )
* 7 => 128
*/
#define STATE_VECTOR_QUEUE_BUFFER_PAGE_EXP 8
/**
* @brief state_vector_queue__init
* @param queue
* @param max
* @return
*/
struct state_vector_queue*
state_vector_queue__init( struct state_vector_queue *queue, int capacity ) {
assert( queue );
queue->buffer = (struct state_vector*)malloc( capacity*sizeof(struct state_vector) );
queue->capacity = capacity;
queue->read_pos = 0;
queue->write_pos = 0;
return queue;
}
/**
* @brief state_vector_queue__free
* @param queue
*/
void
state_vector_queue__free( struct state_vector_queue *queue ) {
assert( queue );
assert( queue->buffer );
free( queue->buffer );
queue->buffer=NULL;
queue->capacity = 0;
queue->read_pos = 0;
queue->write_pos = 0;
}
/**
* @brief state_vector_queue__is_empty
* @param queue
* @return
*/
int
state_vector_queue__is_empty( struct state_vector_queue *queue ) {
assert( queue );
return queue->read_pos==queue->write_pos;
}
/**
* @brief state_vector_queue__enqueue
* @param queue
* @param state
* @param it
* @return
*/
struct state_vector*
state_vector_queue__enqueue( struct state_vector_queue *queue, int state, int it ) {
assert( queue );
assert( queue->buffer );
// calculate next write pos
int next_write_pos= (queue->write_pos+1)%queue->capacity;
// realloc buffer required?
if( next_write_pos == queue->read_pos ) {
int new_capacity = queue->capacity+(1<<STATE_VECTOR_QUEUE_BUFFER_PAGE_EXP);
int added = new_capacity-queue->capacity;
queue->buffer = (struct state_vector*)realloc( queue->buffer, new_capacity*sizeof(struct state_vector) );
assert( queue->buffer );
int *mp = queue->read_pos > queue->write_pos ? &queue->read_pos : &queue->write_pos;
// pulling data apart
memcpy( &queue->buffer[*mp+added], &queue->buffer[*mp], (queue->capacity-added)*sizeof(struct state_vector) );
queue->capacity = new_capacity;
*mp += added;
}
// vector init
struct state_vector* result = &queue->buffer[queue->write_pos];
result->state = state;
result->it = it;
// move write_pos
queue->write_pos=next_write_pos;
return result;
}
/**
* @brief state_vector_queue__dequeue
* @param queue
* @return
*/
struct state_vector*
state_vector_queue__dequeue( struct state_vector_queue *queue ) {
assert( queue );
if( state_vector_queue__is_empty( queue ) )
return NULL;
struct state_vector* result = &queue->buffer[ queue->read_pos ];
queue->read_pos = (queue->read_pos+1) % queue->capacity;
return result;
}

cregex.c

// cregex.c
#include "cregex.h"
#include
#include
#include
// used default heap capacity
#define CREGREX_STATE_HEAP_CAPACITY 128
// used default queue capacity
#define CREGREX_STATE_VECTOR_QUEUE_CAPACITY 128
// internal stack size for nested groups
#define CREGREX_STATE_STACK_SIZE 64
// deadlock counter
#define CREGREX_MAX_DEAD_LOCK_COUNT 8192
#define ASSERT_ERROR_NOT_IMPLEMENTED 0
/**
* @brief cregex__compile
* @param cregex
* @param pattern
* @return
*/
struct cregex*
cregex__compile( struct cregex *cregex, const char *pattern ) {
// heap initialisieren
state_heap__init( &cregex->heap, CREGREX_STATE_HEAP_CAPACITY );
// proc_queue initialisieren
state_vector_queue__init( &cregex->proc_queue, CREGREX_STATE_VECTOR_QUEUE_CAPACITY );
// init struct
cregex->pattern = pattern;
cregex->text = NULL;
cregex->length = 0;
cregex->it = 0;
cregex->start_it = -1;
cregex->stop_it = -1;
cregex->start_state = state_heap__new( &cregex->heap, STATE_COMMAND_LINK );
int last_start_or= -1;
int new_state = -1;
int previous_state=-1;
// sigma = next state to use
int sigma = state_heap__new( &cregex->heap, STATE_COMMAND_LINK );
cregex->heap.buffer[ cregex->start_state ].child = sigma;
// last_start stack for nested groups
int state_stack[CREGREX_STATE_STACK_SIZE];
int state_stack_pointer=0;
// create state tree
int escape_next=0;
int add_command=-1;
int not_command=0;
const char *p;
for( p=pattern; *p; ++p) {
if( !escape_next ) {
// parse char
switch( *p ) {
case '\\': // escape next
escape_next=1;
break;
case '|': // STOP last_start->new_state
assert( last_start_or>=0 );
if( state_stack_pointer>0 ) {
cregex->heap.buffer[ sigma ].child = state_stack[ state_stack_pointer-1 ];
}
sigma = state_heap__new(&cregex->heap, STATE_COMMAND_LINK);
state_heap__append( &cregex->heap, last_start_or, sigma );
break;
case '[': // char declaration till ]
previous_state = new_state;
new_state = sigma;
sigma = state_heap__new(&cregex->heap, STATE_COMMAND_LINK);
if( last_start_or // parse char declaration []
for(; *p; ++p) {
if( !escape_next ) {
switch( *p ) {
case '\\': escape_next=1; break;
case '^': ++not_command; break;
case ']': goto exit_for;
default:
if( not_command ) {
add_command=STATE_COMMAND_NOT_CHAR + *p;
} else {
add_command=STATE_COMMAND_CHAR + *p;
}
break;
}
} else {
add_command=*p;
escape_next=0;
}
// append Cn in new_state->child list
if(add_command>=0 ) {
int Cn = state_heap__new(&cregex->heap, add_command);
cregex->heap.buffer[ Cn ].child = sigma;
cregex->heap.buffer[ Cn ].next = -1;
if( cregex->heap.buffer[new_state].child==-1 )
cregex->heap.buffer[new_state].child = Cn;
else
state_heap__append( &cregex->heap, cregex->heap.buffer[new_state].child, Cn );
not_command=0;
add_command=-1;
}
}
exit_for:
assert(*p);
break;
case ']': // char declaration end
assert(0);
break;
case '{': // {min,max}
{
int min=0,max=0;
sscanf( p,"%u,%u}", &min, &max );
while( *p && *p!='}') ++p;
// TODO...
} break;
case '}':
assert(0);
break;
case '(': // open group
assert(state_stack_pointer+1<CREGREX_STATE_STACK_SIZE);
add_command = STATE_COMMAND_PUSH_GROUP;
state_stack[ state_stack_pointer++ ] = last_start_or;
state_stack[ state_stack_pointer++ ] = state_heap__new(&cregex->heap, STATE_COMMAND_LINK);
last_start_or=-1;
break;
case ')': // close group
assert(state_stack_pointer>0);
if( state_stack_pointer>0 ) {
cregex->heap.buffer[ sigma ].child = state_stack[ state_stack_pointer-1 ];
}
add_command = STATE_COMMAND_POP_GROUP;
sigma = state_stack[ --state_stack_pointer ];
last_start_or = state_stack[ --state_stack_pointer ];
break;
case '+': // repeat previous
assert(new_state>=0);
previous_state = new_state;
new_state = sigma;
sigma = state_heap__new(&cregex->heap, STATE_COMMAND_LINK);
cregex->heap.buffer[ new_state ].command = STATE_COMMAND_LINK;
cregex->heap.buffer[ new_state ].child = sigma;
cregex->heap.buffer[ new_state ].next = previous_state;
break;
case '*': // repeat or empty
assert(new_state>=0);
cregex->heap.buffer[ new_state ].child = new_state;
cregex->heap.buffer[ new_state ].next = sigma;
break;
case '?': // {0,1}
assert(new_state>=0);
cregex->heap.buffer[ new_state ].child = sigma;
cregex->heap.buffer[ new_state ].next = sigma;
break;
case '.': // any
add_command = STATE_COMMAND_ANY;
break;
default: // char
add_command = STATE_COMMAND_CHAR + *p;
break;
}
} else {
// parse escaped char
switch( *p ) {
case 'd': // decimal
add_command = STATE_COMMAND_NUMBER;
break;
case 'w': // word
add_command = STATE_COMMAND_WORD;
break;
case 's': // whitespace
add_command = STATE_COMMAND_WHITESPACE;
break;
case 'D': // decimal
add_command = STATE_COMMAND_NOT_NUMBER;
break;
case 'W': // word
add_command = STATE_COMMAND_NOT_WORD;
break;
case 'S': // whitespace
add_command = STATE_COMMAND_NOT_WHITESPACE;
break;
default: // escaped char
add_command = STATE_COMMAND_CHAR + *p;
break;
}
escape_next = 0;
}
// append add_command
if( add_command>=0 ) {
previous_state = new_state;
new_state = sigma;
sigma = state_heap__new(&cregex->heap, STATE_COMMAND_LINK);
cregex->heap.buffer[ new_state ].command = add_command;
cregex->heap.buffer[ new_state ].child = sigma;
cregex->heap.buffer[ new_state ].next = -1;
if( last_start_or add_command=-1;
}
}
// check group consistency
if( state_stack_pointer>0 ) {
fprintf( stderr, "[!!] cregex__compile could not compile %s",pattern);
assert(state_stack_pointer==0);
}
return cregex;
}
/**
* @brief cregex__free
* @param cregex
*/
void
cregex__free( struct cregex *cregex ) {
state_heap__free( &cregex->heap );
state_vector_queue__free( &cregex->proc_queue );
}
/**
* @brief cregex__reset
* @param cregex
*/
void
cregex__reset( struct cregex *cregex ) {
assert( cregex );
// reset parameter
cregex->start_it = -1;
cregex->stop_it = -1;
cregex->it = 0;
cregex->proc_queue.read_pos = cregex->proc_queue.write_pos = 0;
// enqueue start states at "it=0"
int index;
for( index=cregex->start_state; index>=0; index=cregex->heap.buffer[index].next ) {
state_vector_queue__enqueue( &cregex->proc_queue, index, cregex->it );
}
}
/**
* @brief cregex__match
* @param cregex
* @param text
* @return
*/
int
cregex__match( struct cregex *cregex, const char *text ) {
assert( cregex );
// set text data
cregex->text = text;
cregex->length = strlen(text);
// reset search vector
cregex__reset( cregex );
// search fitting occurance: start_it must be <=0 and stop_it = length
while( cregex__find_next( cregex ) && cregex->start_it<=0 && cregex->stop_it < cregex->length ) {
if( state_vector_queue__is_empty( &cregex->proc_queue ) )
break;
};
// check match
return cregex->start_it <= 0 && cregex->stop_it == cregex->length;
}
/**
* @brief cregex__find_next
* @param cregex
* @param text
* @return =0 false | >0=true
*/
int
cregex__find_next( struct cregex *cregex ) {
assert( cregex );
assert( cregex->text );
// Stop Signal
int found_stop=0;
// deadlock counter
int dead_lock_counter=0;
if( state_vector_queue__is_empty( &cregex->proc_queue ) ) {
int next_pos = cregex->start_it++;
cregex__reset( cregex );
cregex->it = next_pos;
}
// process queue
while( !state_vector_queue__is_empty( &cregex->proc_queue ) && !found_stop ) {
struct state_vector* v= state_vector_queue__dequeue( &cregex->proc_queue );
// assert if deadlock occours
assert( ++dead_lock_counter<CREGREX_MAX_DEAD_LOCK_COUNT );
// state in queue without any children => STOP
if( cregex->heap.buffer[v->state].child==-1 ) {
cregex->stop_it = v->it;
++found_stop;
}
// match & enqueue
int index;
for( index=cregex->heap.buffer[v->state].child; index>=0; index=cregex->heap.buffer[index].next ) {
// fetch command
int cmd = cregex->heap.buffer[index].command;
// fetch char or -1
int c = (v->it>=0 && v->itlength) ? cregex->text[v->it] : -1000;
int add_char = 0;
// process state-command
switch( cmd ) {
case STATE_COMMAND_LINK:
state_vector_queue__enqueue( &cregex->proc_queue, index, v->it );
break;
case STATE_COMMAND_PUSH_GROUP:
state_vector_queue__enqueue( &cregex->proc_queue, index, v->it );
break;
case STATE_COMMAND_POP_GROUP:
state_vector_queue__enqueue( &cregex->proc_queue, index, v->it );
break;
case STATE_COMMAND_BEGIN:
if( v->it==0 )
state_vector_queue__enqueue( &cregex->proc_queue, index, v->it );
break;
case STATE_COMMAND_END:
if( v->it==cregex->length )
state_vector_queue__enqueue( &cregex->proc_queue, index, v->it );
break;
case STATE_COMMAND_ANY:
if( c>=0 )
++add_char;
break;
case STATE_COMMAND_NUMBER:
if( c>=0 && c>='0' && c<='9' )
++add_char;
break;
case STATE_COMMAND_WORD:
if( c>=0 && ( (c>='A' && c<='Z') || (c>='a' && c<='z') || (c>='0' && c<='9') || c=='_' ) )
++add_char;
break;
case STATE_COMMAND_WHITESPACE:
if( c>=0 && ( c==' ' || c=='\t' || c=='\n' || c=='\r') )
++add_char;
break;
case STATE_COMMAND_NOT_NUMBER:
if( c>=0 && !(c>='0' && c<='9') )
++add_char;
break;
case STATE_COMMAND_NOT_WORD:
if( c>=0 && !( (c>='A' && c<='Z') || (c>='a' && c<='z') || (c>='0' && c<='9') || c=='_' ) )
++add_char;
break;
case STATE_COMMAND_NOT_WHITESPACE:
if( c>=0 && !( c==' ' || c=='\t' || c=='\n' || c=='\r') )
++add_char;
break;
default:
if( cmd==c || (cmd>=STATE_COMMAND_NOT_CHAR && (cmd-STATE_COMMAND_NOT_CHAR)!=c ) )
++add_char;
break;
}
// add single state
if( add_char ) {
if( cregex->start_it==-1 ) cregex->start_it = v->it;
state_vector_queue__enqueue( &cregex->proc_queue, index, v->it+1 );
}
}
}
return found_stop;
}
/**
* @brief cregex__debug
* @param cregex
*/
void
cregex__debug( struct cregex *cregex ) {
assert( cregex );
printf("\ncregex__debug::heap %p size %i capacity %i {%i,%i} length %i\n",
cregex->heap.buffer, cregex->heap.count, cregex->heap.capacity, cregex->start_it, cregex->stop_it, cregex->length );
int i;
for(i=0;iheap.count;++i) {
printf(" [%i] cmd:%4i next(%3i) child(%3i)\n",
i, cregex->heap.buffer[i].command, cregex->heap.buffer[i].next, cregex->heap.buffer[i].child );
}
}

Edit: Codeformatierung angepasst, Bilder eingefügt
Edit2: Es handelt sich bei dieser Implementierung natürlich um einen NFA und nicht um einen DFA – dazu fehlt noch eine “state” Zusammenfassung im compile Schritt

RSA Testanwendung

So, nach dem ich gestern Abend über pgp bzw public/private key Verschlüsselung gestolpert bin musste ich unbedingt noch eine kleine Testanwendung dazu Implementieren. Performant und sicher ist sicherlich etwas anderes aber Spaß hat es trotzdem gemacht 😀

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>

// Prototypen
int is_prime( int p );
int random( int min, int max );
int random_prime( int min, int max );
int random_df( int n );
int inverse_mod( int n );
int ggT( int a, int b );
int bin_mod_exp( int x, int k, int m);

int build_keys( int &e, int &d, int &N );
int encode( const char *message, int *encoded, int e, int N );
int decode( int *encoded, int c, char *decoded, int d, int N );


/**
  RSA Test
  **/
int main(int argc, char**argv ) {
const char* message = "Hallo Welt oder was!";
int encoded[256];
char decoded[256];

srand( time(NULL) );

// 1. Private {d|N} & Public {e|N} Schlüssel Generieren
int e, d, N;
build_keys( e, d, N );

// 2. Text Verschluesseln
int c = encode( message, encoded, e, N );
printf("message=>encoded ok\n");

// 3. Text Entschlüsseln
decode( encoded, c, decoded, d, N );
printf("encoded=>decoded ok\n");

// Ausgabe
printf("decoded:\n %s\n", decoded );
return 0;
}

/**
  Einfache Zufallszahl
  **/
int random( int min, int max ) {
return min+(rand()%(max-min));
}

/**
  Primzahltest
  **/
int is_prime( int n ) {
int p,q;
if( !(n%2) ) return 0;
for(p=3, q=sqrt(n); (n%p) && p<q; p+=2 );
return p>=q;
}

/**
  Zufällige Primzahl zwischen min und max
  */
int random_prime( int min, int max ) {
int R;
while( !is_prime(R=random(min,max)) );
return R;
}

/**
  größter gemeinsamer Teiler von a und b
  **/
int ggT( int a, int b ) {
int r;
while( (r=a%b) ) {
a=b;
b=r;
}
return b;
}

/**
  zufallszahl mit keinem gemeinsamen Teiler zu n
  **/
int random_df( int n ) {
int r=0;
while( ggT( (r=random(1,n)), n )>1 );
return r;
}

/**
  InversMultiplikatives Modulo
  **/
int inverse_mod( int a, int n ) {
long k;
for(k=1; (k*a % n)!=1 ; ++k );
return k;
}

/**
  x^k % m
  **/
int bin_mod_exp( int x, int k, int m) {
long res = 1;
long pot = x;
while( k > 0 ) {
if( (k%2) )
res = res*pot % m;
pot = pot*pot % m;
k >>=1;
}
return res;
}

/**
    {e;N} public key
    {d;N} private key
  **/
int build_keys( int &e, int &d, int &N ) {
int p,q,phi_N;

p = random_prime( 10000, 20000 );
while( (q = random_prime( 10000, 20000 ))==p );
printf("primes %u;%u\n",p,q);

N = p*q;
phi_N = (p-1)*(q-1);
e = random_df( phi_N );
d = inverse_mod( e, phi_N );

// check
if( ((long)e*(long)d % (long)phi_N) ==1 ) {
printf("build_keys ok\n N=%x\n e=%x\n d=%x\n",N,e,d);
}
return 0;
}

/**
  Verschlüsseln
  C = K^e mod N
  **/
int encode( const char *message, int *encoded, int e, int N ) {
int p;
for( p=0; message[p]; ++p ) {
int K = message[p];
int C = bin_mod_exp( K, e, N);
encoded[p] = C;
}
return p;
}

/**
  Entschlüsseln
  K = C^d mod N
  **/
int decode( int *encoded, int c, char *decoded, int d, int N ) {
int p;
for( p=0; p<c;++p ) {
int C = encoded[p];
int K = bin_mod_exp( C, d, N);
decoded[p] = K;
}
decoded[p] = 0;
return p;
}

"Template" Queue Makro in C

 kurz und knapp:

1. Makro CREATE_QUEUE_H
2. Makro CREATE_QUEUE_C
3. Testfunktion main


#define CREATE_QUEUE_H(type)\
struct _##type##_QueueElement {\
 struct _##type##_QueueElement* next;\
 type data;\
};\
struct _##type##_Queue {\
 int count;\
 struct _##type##_QueueElement* bottom;\
 struct _##type##_QueueElement* top;\
};\
struct _##type##_Queue* _##type##_Queue_New( ); \
void _##type##_Queue_Delete( struct _##type##_Queue* queue );\
void _##type##_Queue_Enqueue( struct _##type##_Queue* queue, type data );\
type _##type##_Queue_Dequeue( struct _##type##_Queue* queue );
 

#define CREATE_QUEUE_C(type)\
struct _##type##_Queue* _##type##_Queue_New( ) {\
 struct _##type##_Queue* queue = (struct _##type##_Queue*)\
malloc(sizeof(struct _##type##_Queue));\
 queue->bottom=queue->top=queue->count=0;\
 return queue;\
}\
void _##type##_Queue_Delete( struct _##type##_Queue* queue ) {\
 free( queue );\
}\
void _##type##_Queue_Enqueue( struct _##type##_Queue* queue, type data ) {\
 struct _##type##_QueueElement* e= (struct _##type##_QueueElement*)\
 malloc(sizeof(struct _##type##_QueueElement));\
 e->next=0;\
 e->data=data;\
 if( !queue->top ) {\
  queue->top=queue->bottom=e;\
 } else {\
  queue->top->next=e; \
  queue->top=e;\
 }\
 ++queue->count;\
}\
type _##type##_Queue_Dequeue( struct _##type##_Queue* queue ) {\
 if( !queue->bottom ) \
  return 0;\
 struct _##type##_QueueElement* e = queue->bottom;\
 type data = e->data;\
 if( !(queue->bottom=e->next) )\
  queue->top=0;\
 free(e);\
 --queue->count;\
 return data;\
}

// Deklaration
CREATE_QUEUE_H(int)

// Implementierung
CREATE_QUEUE_C(int)
 
int main( int argc, char **argv ) {
 struct _int_Queue* queue= _int_Queue_New();
 int i=0;
 for(i=0;i<10;++i) {
  _int_Queue_Enqueue( queue, i );
 }
 while( queue->count>0 ) {
  printf("dequeue %i\n", _int_Queue_Dequeue( queue ) );
 } 
 
 _int_Queue_Delete( queue );
 return 0;
}
 

"Template" Stack in C

Nachfolgend ein Makro Entwurfsmuster für eine einfache Stack Datenstruktur mit Standard Operatoren Push, Pop und At.


// Erzeugt die Stack Deklaration zu dem Datentyp "type"
#define CREATE_STACK_TYPE_H(type)\
    struct _##type##_StackElement {\
        struct _##type##_StackElement* previous;\
        type data;\
    };\
    struct _##type##_Stack {\
        int count;\
        struct _##type##_StackElement* bottom;\
        struct _##type##_StackElement* top;\
    };\
    struct _##type##_Stack* _##type##_Stack_Create();\
    void  _##type##_Stack_Free( struct _##type##_Stack *stack);\
    void  _##type##_Stack_Push( struct _##type##_Stack *stack, type data );\
    type  _##type##_Stack_Pop( struct _##type##_Stack *stack );\
    type  _##type##_Stack_At( struct _##type##_Stack *stack, int index );

// Erzeugt die Stack Implementierung zu dem Datentyp "Type"
#define CREATE_STACK_TYPE_C(type)\
    struct _##type##_Stack* _##type##_Stack_Create(){\
        struct _##type##_Stack* stack = (struct _##type##_Stack*)malloc(sizeof(struct _##type##_Stack));\
        stack->count=stack->bottom=stack->top=0;\
        return stack;\
    }\
    void _##type##_Stack_Free( struct _##type##_Stack *stack){\
        free(stack);\
    }\
    void  _##type##_Stack_Push( struct _##type##_Stack *stack, type data ){\
        struct _##type##_StackElement *stack_element = (struct _##type##_StackElement*)malloc(sizeof(struct _##type##_StackElement));\
        stack_element->previous=stack->top;\
        stack_element->data=data;\
        if( stack->top ) {\
            stack->top=stack_element;\
        } else {\
            stack->bottom=stack->top=stack_element;\
        }\
        ++stack->count;\
    }\
    type _##type##_Stack_Pop( struct _##type##_Stack *stack ){\
        type*data = stack->top->data;\
        struct _##type##_StackElement *stack_element=stack->top;\
        stack->top = stack->top->previous;\
        if( !stack->top ) stack->bottom=0;\
        free(stack_element);\
        --stack->count;\
        return data;\
    }\
    type _##type##_Stack_At( struct _##type##_Stack *stack, int index ) {\
        struct _##type##_StackElement* element=stack->top;\
        for(; element && index>0; --index) {\
            element=element->previous;\
        }\
        return element ? element->data : 0;\
    }


// Deklaration _int_Stack
CREATE_STACK_TYPE_H(int)

// Implementierung _int_Stack
CREATE_STACK_TYPE_C(int)

int main(void){
    struct _int_Stack* stack = _int_Stack_Create();
    int i=0;

    printf("fill stack\n");
    for(i=0;i<10;++i) {
        _int_Stack_Push(stack, i );
    }

    while( stack->top ) {
        printf("pop %i\n", _int_Stack_Pop( stack ) );
    }

    printf("free stack\n");
    _int_Stack_Free( stack );
    return 0;
}


					

“landscape” via displacementmap (test)

– verwendet die vpgl-3 Engine
– benötigt eine heightmap Textur und eine Farbtextur
– verformt ein Statisches Grid x*x anhand der Höhenkarte
– Das Grid bleibt immer unter der Kamera, Bewegung wird über die Texturkoordinaten realisiert.

land.surface

 # vpgl 1.0  
# type vpgl_surface
# name test
# bounding box
aabox -1024 -1024 -1024 2048 2048 2048
# arraybuffer
gen_vertex_array
gen_mesh_square 1024 1 1024
# shader
fragment_shader file://usr/object/land/land.frag
vertex_shader file://usr/object/land/land.vert
link_program
# shader parameter
texture@tex_height file://usr/object/land/terrain.png
texture@tex_color file://usr/object/land/terrain_color.png
#texture@tex_grass file://usr/object/land/terrain_grass.png
#eof

land.js

 function land() {  
f = resm.getResourceObject("file://usr/object/land.frame");
f.initResource();
root.addFrame( f );
var cam_speed = 10;
// mausbewegung auf den Viewport uebertragen
vpgl.signalMouseMoveEvent.connect(
function(mx,my,dx,dy,buttons) {
var w=vpgl.getScreenWidth()/2;
var h=vpgl.getScreenHeight()/2;
var fx=(mx-w)*(mx-w)/(w*w*1000);
var fy=(my-h)*(my-h)/(h*h*1000);
if( buttons==0 ){
if( dx!=0 ) viewport.rotateY(dx*0.001);
if( dy!=0 ) viewport.rotateX(dy*0.001);
}
}
);
// Tastatursteuerung fuer viewport
vpgl.signalActor.connect(
function(time_overall,time_frame) {
if( vpgl.isKeyPressed( Qt.Key_D ) ) {
viewport.translate( cam_speed*time_frame/250, 0, 0 );
}
if( vpgl.isKeyPressed( Qt.Key_A ) ) {
viewport.translate( cam_speed*-time_frame/250, 0, 0 );
}
if( vpgl.isKeyPressed( Qt.Key_W ) ) {
viewport.translate( 0, 0, cam_speed*-time_frame/250 );
}
if( vpgl.isKeyPressed( Qt.Key_S ) ) {
viewport.translate( 0, 0, cam_speed*time_frame/250 );
}
if( vpgl.isKeyPressed( Qt.Key_Q ) ) {
viewport.rotateZ( -time_frame/1000 );
}
if( vpgl.isKeyPressed( Qt.Key_E ) ) {
viewport.rotateZ( time_frame/1000 );
}
if( vpgl.isKeyPressed( Qt.Key_Y ) ) {
viewport.rotateY( -time_frame/1000 );
}
if( vpgl.isKeyPressed( Qt.Key_C ) ) {
viewport.rotateY( time_frame/1000 );
}
if( vpgl.isKeyPressed( Qt.Key_Up ) ) {
viewport.rotateX( -time_frame/1000 );
}
if( vpgl.isKeyPressed( Qt.Key_Down ) ) {
viewport.rotateX( time_frame/1000 );
}
}
);
}

Vertex Shader

 #version 150  
in vec3 in_Vertex;
out vec2 ex_Coord;
uniform sampler2D tex_height; // heightmap
uniform vec3 cam_pos; // cam position
uniform mat4 proj_matrix; // projection matrix
uniform mat4 modelview_matrix; // modelview matrix
 void main(void) {  
      float scale = sqrt(cam_pos.y)*0.125;  
vec2 nv = in_Vertex.xz- vec2(0.5,0.5);
ex_Coord = nv*scale +cam_pos.xz/2048.0;
mat4 m = modelview_matrix;
m[3][0]= 0.0;
m[3][1]= 0.0;
m[3][2]= 0.0;
vec4 v = m * vec4(
nv.x*512.0,
(texture2D(tex_height,ex_Coord).r-0.5)*64.0/scale,
nv.y*512.0,
1.0
);
gl_Position = proj_matrix * v;
}

Fragment Shader

 #version 150  
precision highp float;
uniform sampler2D tex_color;
in vec2 ex_Coord;
out vec4 gl_FragColor;
void main(void) {
gl_FragColor = vec4( texture2D( tex_color, ex_Coord ).rgb, 1.0);
}

Ergebnis