Technical debt: cleaned up things in the assembler that should've used Buffer.
authorRyan C. Gordon <icculus@icculus.org>
Wed, 10 Nov 2010 00:52:01 -0500
changeset 946 16fec3a3f687
parent 945 f00ea3986db8
child 947 16af6e2b2ada
Technical debt: cleaned up things in the assembler that should've used Buffer.
mojoshader_assembler.c
mojoshader_common.c
mojoshader_internal.h
--- a/mojoshader_assembler.c	Tue Nov 09 05:05:41 2010 -0500
+++ b/mojoshader_assembler.c	Wed Nov 10 00:52:01 2010 -0500
@@ -54,13 +54,9 @@
     uint32 tokenbuf[16];    // bytecode tokens!
     int tokenbufpos;        // bytecode tokens!
     DestArgInfo dest_arg;
-    uint32 *output;
-    SourcePos *token_to_source;
-    uint8 *ctab;
-    uint32 ctab_len;
-    uint32 ctab_allocation;
-    size_t output_len;
-    size_t output_allocation;
+    Buffer *output;
+    Buffer *token_to_source;
+    Buffer *ctab;
 } Context;
 
 
@@ -228,50 +224,24 @@
     return ctx->tokenval;
 } // nexttoken
 
-// !!! FIXME: hashmap?
-static inline void add_token_sourcepos(Context *ctx, const size_t idx)
-{
-    unsigned int pos = 0;
-    const char *fname = preprocessor_sourcepos(ctx->preprocessor, &pos);
-    ctx->token_to_source[idx].line = pos;
-    ctx->token_to_source[idx].filename = fname;  // cached in preprocessor!
-} // add_token_sourcepos
 
-
-// !!! FIXME: use BufferList.
 static void output_token_noswap(Context *ctx, const uint32 token)
 {
-    if (isfail(ctx))
-        return;
-
-    if (ctx->output_len >= ctx->output_allocation)
+    if (!isfail(ctx))
     {
-        const size_t output_alloc_bump = 1024;  // that's tokens, not bytes.
-        const size_t newsize = ctx->output_allocation + output_alloc_bump;
-        void *ptr;
+        buffer_append(ctx->output, &token, sizeof (token));
 
-        ptr = Malloc(ctx, newsize * sizeof (uint32));
-        if (ptr == NULL)
-            return;
-        if (ctx->output_len > 0)
-            memcpy(ptr, ctx->output, ctx->output_len * sizeof (uint32));
-        Free(ctx, ctx->output);
-        ctx->output = (uint32 *) ptr;
-
-        ptr = Malloc(ctx, newsize * sizeof (SourcePos));
-        if (ptr == NULL)
-            return;
-        if (ctx->output_len > 0)
-            memcpy(ptr, ctx->token_to_source, ctx->output_len * sizeof (SourcePos));
-        Free(ctx, ctx->token_to_source);
-        ctx->token_to_source = (SourcePos *) ptr;
-
-        ctx->output_allocation = newsize;
+        // We only need a list of these that grows throughout processing, and
+        //  is flattened for reference at the end of the run, so we use a
+        //  Buffer. It's sneaky!
+        unsigned int pos = 0;
+        const char *fname = preprocessor_sourcepos(ctx->preprocessor, &pos);
+        SourcePos srcpos;
+        memset(&srcpos, '\0', sizeof (SourcePos));
+        srcpos.line = pos;
+        srcpos.filename = fname;  // cached in preprocessor!
+        buffer_append(ctx->token_to_source, &srcpos, sizeof (SourcePos));
     } // if
-
-    ctx->output[ctx->output_len] = token;
-    add_token_sourcepos(ctx, ctx->output_len);
-    ctx->output_len++;
 } // output_token_noswap
 
 
@@ -289,8 +259,6 @@
     {
         const uint32 tokencount = (len / 4) + ((len % 4) ? 1 : 0);
         output_token(ctx, 0xFFFE | (tokencount << 16));
-        // !!! FIXME: we can probably just use use modulo and do this without
-        // !!! FIXME:  a tight loop with BufferList.
         while (len >= 4)
         {
             output_token_noswap(ctx, *((const uint32 *) buf));
@@ -1431,6 +1399,22 @@
 } // parse_token
 
 
+static void destroy_context(Context *ctx)
+{
+    if (ctx != NULL)
+    {
+        MOJOSHADER_free f = ((ctx->free != NULL) ? ctx->free : MOJOSHADER_internal_free);
+        void *d = ctx->malloc_data;
+        preprocessor_end(ctx->preprocessor);
+        errorlist_destroy(ctx->errors);
+        buffer_destroy(ctx->ctab);
+        buffer_destroy(ctx->token_to_source);
+        buffer_destroy(ctx->output);
+        f(ctx, d);
+    } // if
+} // destroy_context
+
+
 static Context *build_context(const char *filename,
                               const char *source, unsigned int sourcelen,
                               const MOJOSHADER_preprocessorDefine *defines,
@@ -1454,12 +1438,19 @@
     ctx->malloc_data = d;
     ctx->parse_phase = MOJOSHADER_PARSEPHASE_NOTSTARTED;
 
+    const size_t outblk = sizeof (uint32) * 4 * 64; // 64 4-token instrs.
+    ctx->output = buffer_create(outblk, MallocBridge, FreeBridge, ctx);
+    if (ctx->output == NULL)
+        goto build_context_failed;
+
+    const size_t mapblk = sizeof (SourcePos) * 4 * 64; // 64 * 4-tokens.
+    ctx->token_to_source = buffer_create(mapblk, MallocBridge, FreeBridge, ctx);
+    if (ctx->token_to_source == NULL)
+        goto build_context_failed;
+
     ctx->errors = errorlist_create(MallocBridge, FreeBridge, ctx);
     if (ctx->errors == NULL)
-    {
-        f(ctx, d);
-        return NULL;
-    } // if
+        goto build_context_failed;
 
     ctx->preprocessor = preprocessor_start(filename, source, sourcelen,
                                            include_open, include_close,
@@ -1467,37 +1458,16 @@
                                            MallocBridge, FreeBridge, ctx);
 
     if (ctx->preprocessor == NULL)
-    {
-        errorlist_destroy(ctx->errors);
-        f(ctx, d);
-        return NULL;
-    } // if
+        goto build_context_failed;
 
     return ctx;
+
+build_context_failed:  // ctx is allocated and zeroed before this is called.
+    destroy_context(ctx);
+    return NULL;
 } // build_context
 
 
-static void destroy_context(Context *ctx)
-{
-    if (ctx != NULL)
-    {
-        MOJOSHADER_free f = ((ctx->free != NULL) ? ctx->free : MOJOSHADER_internal_free);
-        void *d = ctx->malloc_data;
-        if (ctx->errors != NULL)
-            errorlist_destroy(ctx->errors);
-        if (ctx->preprocessor != NULL)
-            preprocessor_end(ctx->preprocessor);
-        if (ctx->output != NULL)
-            f(ctx->output, d);
-        if (ctx->token_to_source != NULL)
-            f(ctx->token_to_source, d);
-        if (ctx->ctab != NULL)
-            f(ctx->ctab, d);
-        f(ctx, d);
-    } // if
-} // destroy_context
-
-
 static const MOJOSHADER_parseData *build_failed_assembly(Context *ctx)
 {
     assert(isfail(ctx));
@@ -1517,8 +1487,10 @@
 
     retval->error_count = errorlist_count(ctx->errors);
     retval->errors = errorlist_flatten(ctx->errors);
+
     if (ctx->out_of_memory)
     {
+        Free(ctx, retval->errors);
         Free(ctx, retval);
         return &MOJOSHADER_out_of_mem_data;
     } // if
@@ -1529,48 +1501,17 @@
 
 static uint32 add_ctab_bytes(Context *ctx, const uint8 *bytes, const size_t len)
 {
+    if (isfail(ctx))
+        return 0;
+
     const size_t extra = CTAB_SIZE + sizeof (uint32);
-    if (len <= (ctx->ctab_len - extra))
-    {
-        uint8 *ptr = ctx->ctab + extra;
-        if (len == 0)
-            return ( (uint32) (ptr - ctx->ctab) ) - sizeof (uint32);
-        else if ((len == 1) && ((ptr = (uint8 *) memchr(ptr, bytes[0], ctx->ctab_len - len)) != NULL))
-            return ( (uint32) (ptr - ctx->ctab) ) - sizeof (uint32);
-        else  // search for the string of bytes...
-        {
-            while ((ptr = (uint8 *) memchr(ptr, bytes[0], ctx->ctab_len - len)) != NULL)
-            {
-                if (memcmp(ptr, bytes, len) == 0)  // this is it?
-                    return ( (uint32) (ptr - ctx->ctab) ) - sizeof (uint32);
-                ptr++;  // !!! FIXME: should this be "ptr += len;"  ?
-            } // while
-        } // else
-    } // if
+    const ssize_t pos = buffer_find(ctx->ctab, extra, bytes, len);
+    if (pos >= 0)  // blob is already in here.
+        return ((uint32) pos) - sizeof (uint32);
 
     // add it to the byte pile...
-
-    // verify allocation.
-    const size_t newsize = (ctx->ctab_len + len);
-    if (ctx->ctab_allocation < newsize)
-    {
-        const size_t additional = 4 * 1024;
-        while (ctx->ctab_allocation < newsize)
-            ctx->ctab_allocation += additional;
-        void *ptr = Malloc(ctx, ctx->ctab_allocation);
-        if (ptr == NULL)
-            return 0;
-        if (ctx->ctab != NULL)
-        {
-            memcpy(ptr, ctx->ctab, ctx->ctab_len);
-            Free(ctx, ctx->ctab);
-        } // if
-        ctx->ctab = (uint8 *) ptr;
-    } // if
-
-    const uint32 retval = ctx->ctab_len - sizeof (uint32);
-    memcpy(ctx->ctab + ctx->ctab_len, bytes, len);
-    ctx->ctab_len += len;
+    const uint32 retval = ((uint32) buffer_size(ctx->ctab)) - sizeof (uint32);
+    buffer_append(ctx->ctab, bytes, len);
     return retval;
 } // add_ctab_bytes
 
@@ -1656,10 +1597,20 @@
 static void output_ctab(Context *ctx, const MOJOSHADER_symbol *symbols,
                         unsigned int symbol_count, const char *creator)
 {
-    ctx->ctab_len = CTAB_SIZE + sizeof (uint32);
+    const size_t tablelen = CTAB_SIZE + sizeof (uint32);
+
+    ctx->ctab = buffer_create(256, MallocBridge, FreeBridge, ctx);
+    if (ctx->ctab == NULL)
+        return;  // out of memory.
 
-    uint8 bytes[CTAB_SIZE + sizeof (uint32)];
-    uint32 *table = (uint32 *) bytes;
+    uint32 *table = (uint32 *) buffer_reserve(ctx->ctab, tablelen);
+    if (table == NULL)
+    {
+        buffer_destroy(ctx->ctab);
+        ctx->ctab = NULL;
+        return;  // out of memory.
+    } // if
+
     *(table++) = SWAP32(CTAB_ID);
     *(table++) = SWAP32(CTAB_SIZE);
     *(table++) = SWAP32(add_ctab_string(ctx, creator));
@@ -1668,13 +1619,17 @@
     *(table++) = SWAP32(add_ctab_info(ctx, symbols, symbol_count));
     *(table++) = SWAP32(0);  // build flags.
     *(table++) = SWAP32(add_ctab_string(ctx, ""));  // !!! FIXME: target?
-    memcpy(ctx->ctab, bytes, sizeof (bytes));
-    output_comment_bytes(ctx, ctx->ctab, ctx->ctab_len);
 
-    Free(ctx, ctx->ctab);
+    const size_t ctablen = buffer_size(ctx->ctab);
+    uint8 *buf = (uint8 *) buffer_flatten(ctx->ctab);
+    if (buf != NULL)
+    {
+        output_comment_bytes(ctx, buf, ctablen);
+        Free(ctx, buf);
+    } // if
+
+    buffer_destroy(ctx->ctab);
     ctx->ctab = NULL;
-    ctx->ctab_len = 0;
-    ctx->ctab_allocation = 0;
 } // output_ctab
 
 
@@ -1703,6 +1658,80 @@
 } // output_comments
 
 
+static const MOJOSHADER_parseData *build_final_assembly(Context *ctx)
+{
+    if (isfail(ctx))
+        return build_failed_assembly(ctx);
+
+    // get the final bytecode!
+    const unsigned int output_len = (unsigned int) buffer_size(ctx->output);
+    unsigned char *bytecode = buffer_flatten(ctx->output);
+    buffer_destroy(ctx->output);
+    ctx->output = NULL;
+
+    if (bytecode == NULL)
+        return build_failed_assembly(ctx);
+
+    // This validates the shader; there are lots of things that are
+    //  invalid, but will successfully parse in the assembler,
+    //  generating bad bytecode; this will catch them without us
+    //  having to duplicate most of the validation here.
+    // It also saves us the trouble of duplicating all the other work,
+    //  like setting up the uniforms list, etc.
+    MOJOSHADER_parseData *retval = (MOJOSHADER_parseData *)
+                            MOJOSHADER_parse(MOJOSHADER_PROFILE_BYTECODE,
+                                    bytecode, output_len, NULL, 0,
+                                    ctx->malloc, ctx->free, ctx->malloc_data);
+    Free(ctx, bytecode);
+
+    SourcePos *token_to_src = NULL;
+    if (retval->error_count > 0)
+        token_to_src = (SourcePos *) buffer_flatten(ctx->token_to_source);
+    buffer_destroy(ctx->token_to_source);
+    ctx->token_to_source = NULL;
+
+    if (retval->error_count > 0)
+    {
+        if (token_to_src == NULL)
+        {
+            assert(ctx->out_of_memory);
+            MOJOSHADER_freeParseData(retval);
+            return build_failed_assembly(ctx);
+        } // if
+
+        // on error, map the bytecode back to a line number.
+        int i;
+        for (i = 0; i < retval->error_count; i++)
+        {
+            MOJOSHADER_error *error = &retval->errors[i];
+            if (error->error_position >= 0)
+            {
+                assert(retval != &MOJOSHADER_out_of_mem_data);
+                assert((error->error_position % sizeof (uint32)) == 0);
+
+                const size_t pos = error->error_position / sizeof(uint32);
+                if (pos >= output_len)
+                    error->error_position = -1;  // oh well.
+                else
+                {
+                    const SourcePos *srcpos = &token_to_src[pos];
+                    Free(ctx, (void *) error->filename);
+                    char *fname = NULL;
+                    if (srcpos->filename != NULL)
+                        fname = StrDup(ctx, srcpos->filename);
+                    error->error_position = srcpos->line;
+                    error->filename = fname;  // may be NULL, that's okay.
+                } // else
+            } // if
+        } // for
+
+        Free(ctx, token_to_src);
+    } // if
+
+    return retval;
+} // build_final_assembly
+
+
 // API entry point...
 
 const MOJOSHADER_parseData *MOJOSHADER_assemble(const char *filename,
@@ -1716,7 +1745,7 @@
                              MOJOSHADER_includeClose include_close,
                              MOJOSHADER_malloc m, MOJOSHADER_free f, void *d)
 {
-    MOJOSHADER_parseData *retval = NULL;
+    const MOJOSHADER_parseData *retval = NULL;
     Context *ctx = NULL;
 
     if ( ((m == NULL) && (f != NULL)) || ((m != NULL) && (f == NULL)) )
@@ -1739,49 +1768,7 @@
 
     output_token(ctx, 0x0000FFFF);   // end token always 0x0000FFFF.
 
-    if (isfail(ctx))
-        retval = (MOJOSHADER_parseData *) build_failed_assembly(ctx);
-    else
-    {
-        // This validates the shader; there are lots of things that are
-        //  invalid, but will successfully parse in the assembler, generating
-        //  bad bytecode; this will catch them without us having to
-        //  duplicate most of the validation here.
-        // It also saves us the trouble of duplicating all the other work,
-        //  like setting up the uniforms list, etc.
-        retval = (MOJOSHADER_parseData *)
-                        MOJOSHADER_parse(MOJOSHADER_PROFILE_BYTECODE,
-                                      (const unsigned char *) ctx->output,
-                                      ctx->output_len * sizeof (uint32),
-                                      NULL, 0, m, f, d);
-
-        // on error, map the bytecode back to a line number.
-        int i;
-        for (i = 0; i < retval->error_count; i++)
-        {
-            MOJOSHADER_error *error = &retval->errors[i];
-            if (error->error_position >= 0)
-            {
-                assert(retval != &MOJOSHADER_out_of_mem_data);
-                assert((error->error_position % sizeof (uint32)) == 0);
-
-                const size_t pos = error->error_position / sizeof (uint32);
-                if (pos >= ctx->output_len)
-                    error->error_position = -1;  // oh well.
-                else
-                {
-                    const SourcePos *srcpos = &ctx->token_to_source[pos];
-                    Free(ctx, (void *) error->filename);
-                    char *fname = NULL;
-                    if (srcpos->filename != NULL)
-                        fname = StrDup(ctx, srcpos->filename);
-                    error->error_position = srcpos->line;
-                    error->filename = fname;  // may be NULL, that's okay.
-                } // else
-            } // if
-        } // for
-    } // if
-
+    retval = build_final_assembly(ctx);
     destroy_context(ctx);
     return retval;
 } // MOJOSHADER_assemble
--- a/mojoshader_common.c	Tue Nov 09 05:05:41 2010 -0500
+++ b/mojoshader_common.c	Wed Nov 10 00:52:01 2010 -0500
@@ -558,7 +558,7 @@
 
 typedef struct BufferBlock
 {
-    char *data;
+    uint8 *data;
     size_t bytes;
     struct BufferBlock *next;
 } BufferBlock;
@@ -589,13 +589,59 @@
     return buffer;
 } // buffer_create
 
-int buffer_append(Buffer *buffer, const char *data, size_t len)
+void *buffer_reserve(Buffer *buffer, const size_t len)
 {
     // note that we make the blocks bigger than blocksize when we have enough
     //  data to overfill a fresh block, to reduce allocations.
     const size_t blocksize = buffer->block_size;
 
     if (len == 0)
+        return NULL;
+
+    if (buffer->tail != NULL)
+    {
+        const size_t tailbytes = buffer->tail->bytes;
+        const size_t avail = (tailbytes >= blocksize) ? 0 : blocksize - tailbytes;
+        if (len <= avail)
+        {
+            buffer->tail->bytes += len;
+            buffer->total_bytes += len;
+            assert(buffer->tail->bytes <= blocksize);
+            return buffer->tail->data + tailbytes;
+        } // if
+    } // if
+
+    // need to allocate a new block (even if a previous block wasn't filled,
+    //  so this buffer is contiguous).
+    const size_t bytecount = len > blocksize ? len : blocksize;
+    const size_t malloc_len = sizeof (BufferBlock) + bytecount;
+    BufferBlock *item = (BufferBlock *) buffer->m(malloc_len, buffer->d);
+    if (item == NULL)
+        return NULL;
+
+    item->data = ((uint8 *) item) + sizeof (BufferBlock);
+    item->bytes = len;
+    item->next = NULL;
+    if (buffer->tail != NULL)
+        buffer->tail->next = item;
+    else
+        buffer->head = item;
+    buffer->tail = item;
+
+    buffer->total_bytes += len;
+
+    return item->data;
+} // buffer_reserve
+
+int buffer_append(Buffer *buffer, const void *_data, size_t len)
+{
+    const uint8 *data = (const uint8 *) _data;
+
+    // note that we make the blocks bigger than blocksize when we have enough
+    //  data to overfill a fresh block, to reduce allocations.
+    const size_t blocksize = buffer->block_size;
+
+    if (len == 0)
         return 1;
 
     if (buffer->tail != NULL)
@@ -623,7 +669,7 @@
         if (item == NULL)
             return 0;
 
-        item->data = ((char *) item) + sizeof (BufferBlock);
+        item->data = ((uint8 *) item) + sizeof (BufferBlock);
         item->bytes = len;
         item->next = NULL;
         if (buffer->tail != NULL)
@@ -693,7 +739,7 @@
     buffer->total_bytes = 0;
 } // buffer_empty
 
-char *buffer_flatten(Buffer *buffer)
+void *buffer_flatten(Buffer *buffer)
 {
     char *retval = (char *) buffer->m(buffer->total_bytes + 1, buffer->d);
     if (retval == NULL)
@@ -718,7 +764,7 @@
     return retval;
 } // buffer_flatten
 
-char *buffer_merge(Buffer **buffers, const size_t n, size_t *_len)
+void *buffer_merge(Buffer **buffers, const size_t n, size_t *_len)
 {
     Buffer *first = NULL;
     size_t len = 0;
@@ -778,5 +824,99 @@
     } // if
 } // buffer_destroy
 
+static int blockscmp(BufferBlock *item, const uint8 *data, size_t len)
+{
+    if (len == 0)
+        return 1;  // "match"
+
+    while (item != NULL)
+    {
+        const size_t itemremain = item->bytes;
+        const size_t avail = len < itemremain ? len : itemremain;
+        if (memcmp(item->data, data, avail) != 0)
+            return 0;  // not a match.
+
+        if (len == avail)
+            return 1;   // complete match!
+
+        len -= avail;
+        data += avail;
+        item = item->next;
+    } // while
+
+    return 0;  // not a complete match.
+} // blockscmp
+
+ssize_t buffer_find(Buffer *buffer, const size_t start,
+                    const void *_data, const size_t len)
+{
+    if (len == 0)
+        return 0;  // I guess that's right.
+
+    if (start >= buffer->total_bytes)
+        return -1;  // definitely can't match.
+
+    if (len > (buffer->total_bytes - start))
+        return -1;  // definitely can't match.
+
+    // Find the start point somewhere in the center of a buffer.
+    BufferBlock *item = buffer->head;
+    const uint8 *ptr = item->data;
+    size_t pos = 0;
+    if (start > 0)
+    {
+        while (1)
+        {
+            assert(item != NULL);
+            if ((pos + item->bytes) > start)  // start is in this block.
+            {
+                ptr = item->data + (start - pos);
+                break;
+            } // if
+
+            pos += item->bytes;
+            item = item->next;
+        } // while
+    } // if
+
+    // okay, we're at the origin of the search.
+    assert(item != NULL);
+    assert(ptr != NULL);
+
+    const uint8 *data = (const uint8 *) _data;
+    const uint8 first = *data;
+    while (item != NULL)
+    {
+        const size_t itemremain = item->bytes - ((size_t)(ptr-item->data));
+        ptr = (uint8 *) memchr(ptr, first, itemremain);
+        while (ptr != NULL)
+        {
+            const size_t retval = pos + ((size_t) (ptr - item->data));
+            if (len == 1)
+                return retval;  // we're done, here it is!
+
+            const size_t itemremain = item->bytes - ((size_t)(ptr-item->data));
+            const size_t avail = len < itemremain ? len : itemremain;
+            if ((avail == 0) || (memcmp(ptr, data, avail) == 0))
+            {
+                // okay, we've got a (sub)string match! Move to the next block.
+                // check all blocks until we get a complete match or a failure.
+                if (blockscmp(item->next, data+avail, len-avail))
+                    return (ssize_t) retval;
+            } // if
+
+            // try again, further in this block.
+            ptr = (uint8 *) memchr(ptr + 1, first, itemremain - 1);
+        } // while
+
+        pos += item->bytes;
+        item = item->next;
+        if (item != NULL)
+            ptr = item->data;
+    } // while
+
+    return -1;  // no match found.
+} // buffer_find
+
 // end of mojoshader_common.c ...
 
--- a/mojoshader_internal.h	Tue Nov 09 05:05:41 2010 -0500
+++ b/mojoshader_internal.h	Wed Nov 10 00:52:01 2010 -0500
@@ -214,14 +214,17 @@
 
 typedef struct Buffer Buffer;
 Buffer *buffer_create(size_t blksz,MOJOSHADER_malloc m,MOJOSHADER_free f,void *d);
-int buffer_append(Buffer *buffer, const char *data, size_t len);
+void *buffer_reserve(Buffer *buffer, const size_t len);
+int buffer_append(Buffer *buffer, const void *_data, size_t len);
 int buffer_append_fmt(Buffer *buffer, const char *fmt, ...) ISPRINTF(2,3);
 int buffer_append_va(Buffer *buffer, const char *fmt, va_list va);
 size_t buffer_size(Buffer *buffer);
 void buffer_empty(Buffer *buffer);
-char *buffer_flatten(Buffer *buffer);
-char *buffer_merge(Buffer **buffers, const size_t n, size_t *_len);
+void *buffer_flatten(Buffer *buffer);
+void *buffer_merge(Buffer **buffers, const size_t n, size_t *_len);
 void buffer_destroy(Buffer *buffer);
+ssize_t buffer_find(Buffer *buffer, const size_t start,
+                    const void *data, const size_t len);