FS#4755: Wikiviewer plugin

* Import of Avi Eisenberg's latest patch (dated May 27 '13)
* Probably not mergeable due to copyright issues

Change-Id: I5a0c2879bc0947ef506eaab48d470b04afb7a870

4 files changed, 326 insertions, 0 deletions

diff --git a/apps/plugins/wikiviewer/shared/btsearch.c b/apps/plugins/wikiviewer/shared/btsearch.c
new file mode 100644
index 0000000..9df9479
--- /dev/null
+++ b/apps/plugins/wikiviewer/shared/btsearch.c
@@ -0,0 +1,153 @@
+/***************************************************************************
+ *             __________               __   ___.
+ *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
+ *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
+ *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
+ *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
+ *                     \/            \/     \/    \/            \/
+ * $Id$
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
+ * KIND, either express or implied.
+ *
+ ****************************************************************************/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <time.h>
+#include <stdint.h>
+#include <limits.h>
+#include <string.h>
+#include "utf8_aux.h"
+#include "btsearch.h"
+
+#if 0
+#define DEBUGF printf
+#else
+#define DEBUGF(...)
+#endif
+
+#define ROCKBOX_LITTLE_ENDIAN
+#define KEY_MAXLEN 200
+
+static inline unsigned short swap16(unsigned short value)
+/*
+   result[15..8] = value[ 7..0];
+   result[ 7..0] = value[15..8];
+ */
+{
+    return (value >> 8) | (value << 8);
+}
+
+static inline unsigned long swap32(unsigned long value)
+/*
+   result[31..24] = value[ 7.. 0];
+   result[23..16] = value[15.. 8];
+   result[15.. 8] = value[23..16];
+   result[ 7.. 0] = value[31..24];
+ */
+{
+    unsigned long hi = swap16(value >> 16);
+    unsigned long lo = swap16(value & 0xffff);
+    return (lo << 16) | hi;
+}
+
+#ifdef ROCKBOX_LITTLE_ENDIAN
+#define letoh16(x) (x)
+#define letoh32(x) (x)
+#else
+#define letoh16(x) swap16(x)
+#define letoh32(x) swap32(x)
+#endif
+
+#ifdef BTSEARCH_MAIN
+int main(int argc,char * argv[])
+{
+    if(argc<3)
+        printf("Usage: btsearch <file> <key>\n");
+    else
+    {
+        FILE *fd=fopen(argv[1],"r");
+        uint32_t res_lo;
+        uint32_t res_hi;
+        fseek(fd,0,SEEK_SET);
+        search_btree(fd, argv[2], strlen(argv[2]), 0, &res_lo, &res_hi, false);
+        printf("Result: %d,%d\n",res_lo,res_hi);
+    }
+
+    return 0;
+}
+
+#endif
+
+void search_btree(void* file, const char* key, uint16_t rkeylen, uint32_t globoffs,
+                  uint32_t* res_lo, uint32_t* res_hi, const bool casesense)
+{
+    unsigned char nd_key[KEY_MAXLEN];
+    uint8_t node_flags;
+    uint16_t node_nr_active,i,keylen;
+    uint32_t chldptr;
+    uint64_t dtaptr_lo,dtaptr_hi;
+    fread(&node_flags,sizeof(uint8_t),1,file);
+    fread(&node_nr_active,sizeof(uint16_t),1,file);
+    node_nr_active=letoh16(node_nr_active);
+    if(node_nr_active<1)   /* error */
+        goto err;
+
+    for(i=0; i<node_nr_active; i++)
+    {
+        fread(&dtaptr_lo,sizeof(uint32_t),1,file);
+        dtaptr_lo=letoh32(dtaptr_lo);
+        fread(&dtaptr_hi,sizeof(uint32_t),1,file);
+        dtaptr_hi=letoh32(dtaptr_hi);
+        fread(&chldptr,sizeof(uint32_t),1,file);
+        chldptr=letoh32(chldptr);
+        fread(&keylen,sizeof(uint16_t),1,file);
+        keylen=letoh32(keylen);
+        fread(&nd_key,sizeof(unsigned char),(keylen<KEY_MAXLEN) ? keylen : KEY_MAXLEN,file);
+        if(keylen-((keylen<KEY_MAXLEN) ? keylen : KEY_MAXLEN)>0)
+            fseek(file,keylen-((keylen<KEY_MAXLEN) ? keylen : KEY_MAXLEN),SEEK_CUR);
+
+        keylen=(keylen<KEY_MAXLEN) ? keylen : KEY_MAXLEN;
+
+        nd_key[keylen]=0;
+        DEBUGF("CMP: %s, %s\n", key, nd_key);
+        if(utf8strcnmp(((const unsigned char*)key),((const unsigned char*)nd_key),rkeylen,keylen,casesense)>0)
+            continue;
+
+        if(utf8strcnmp(((const unsigned char*)key),((const unsigned char*)nd_key),rkeylen,keylen,casesense)==0)
+        {
+            DEBUGF("Found! %s\n", nd_key);
+            *res_lo=dtaptr_lo;
+            *res_hi=dtaptr_hi;
+            return;
+        }
+
+        if(chldptr==0||node_flags==1)
+            goto err;
+
+        fseek(file,globoffs+chldptr,SEEK_SET);
+        search_btree(file,key,rkeylen,globoffs,res_lo,res_hi,casesense);
+        return;
+    }
+
+    if(node_flags!=1)   /* node not leaf */
+    {
+        fread(&chldptr,sizeof(uint32_t),1,file);
+        chldptr=letoh32(chldptr);
+        if(chldptr==0)   /* leaf */
+            goto err;
+
+        fseek(file,globoffs+chldptr,SEEK_SET);
+        search_btree(file,key,rkeylen,globoffs,res_lo,res_hi,casesense);
+    }
+
+    return;
+err:
+    *res_lo=*res_hi=0;
+}
diff --git a/apps/plugins/wikiviewer/shared/btsearch.h b/apps/plugins/wikiviewer/shared/btsearch.h
new file mode 100644
index 0000000..07b150b
--- /dev/null
+++ b/apps/plugins/wikiviewer/shared/btsearch.h
@@ -0,0 +1,26 @@
+/***************************************************************************
+ *             __________               __   ___.
+ *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
+ *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
+ *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
+ *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
+ *                     \/            \/     \/    \/            \/
+ * $Id$
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
+ * KIND, either express or implied.
+ *
+ ****************************************************************************/
+
+#ifndef BTSEARCH_H
+#define BTSEARCH_H
+#include <inttypes.h>
+
+void search_btree(void *fp, const char* key, uint16_t rkeylen, uint32_t globoffs,
+                  uint32_t* res_lo, uint32_t* res_hi, const bool casesense);
+#endif
diff --git a/apps/plugins/wikiviewer/shared/utf8_aux.c b/apps/plugins/wikiviewer/shared/utf8_aux.c
new file mode 100644
index 0000000..3b30a7c
--- /dev/null
+++ b/apps/plugins/wikiviewer/shared/utf8_aux.c
@@ -0,0 +1,117 @@
+/***************************************************************************
+ *             __________               __   ___.
+ *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
+ *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
+ *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
+ *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
+ *                     \/            \/     \/    \/            \/
+ * $Id$
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
+ * KIND, either express or implied.
+ *
+ ****************************************************************************/
+
+#include <ctype.h>
+#include "utf8_aux.h"
+
+char utf8strcnmp(const unsigned char *s1, const unsigned char *s2,uint16_t n1,uint16_t n2, const bool casesense)
+{
+    unsigned short c1,c2;
+    const unsigned char *s1p,*s2p;
+    s1p=s1;
+    s2p=s2;
+    for(;; )
+    {
+        if(s1p-s1==n1)
+        {
+            if(n1==n2&&n2==s2p-s2) return 0;
+            else return -1;
+        }
+
+        if(s2p-s2==n2)
+        {
+            /* printf("N1:%u,N2:%u,s1p-s1:%d\n",n1,n2,s1p-s1); */
+            if(n1==n2&&n1==s1p-s1) return 0;
+            else return 1;
+        }
+
+        s1p=utf8decode(s1p,&c1);
+        s2p=utf8decode(s2p,&c2);
+        if(c1==' ') c1='_';
+
+        if(c2==' ') c2='_';
+
+        /* if(s1p-s1==1&&s2p-s2==1&&c1<128&&c2<128){ */
+        if(!casesense && c1<128&&c2<128)
+        {
+            /* printf("TLC\n); */
+            c1=tolower(c1);
+            c2=tolower(c2);
+        }
+
+        if(c1<c2) return -1;
+        else if (c1>c2) return 1;
+    }
+    /* printf("CMPEND\n"); */
+    return 0; /*won't happen*/
+}
+
+/* Decode 1 UTF-8 char and return a pointer to the next char. */
+const unsigned char* utf8decode(const unsigned char *utf8, unsigned short *ucs)
+{
+    unsigned char c = *utf8++;
+    unsigned long code;
+    int tail = 0;
+
+    if ((c <= 0x7f) || (c >= 0xc2))
+    {
+        /* Start of new character. */
+        if (c < 0x80)          /* U-00000000 - U-0000007F, 1 byte */
+            code = c;
+        else if (c < 0xe0)     /* U-00000080 - U-000007FF, 2 bytes */
+        {
+            tail = 1;
+            code = c & 0x1f;
+        }
+        else if (c < 0xf0)     /* U-00000800 - U-0000FFFF, 3 bytes */
+        {
+            tail = 2;
+            code = c & 0x0f;
+        }
+        else if (c < 0xf5)     /* U-00010000 - U-001FFFFF, 4 bytes */
+        {
+            tail = 3;
+            code = c & 0x07;
+        }
+        else
+            /* Invalid size. */
+            code = 0xfffd;
+
+        while (tail-- && ((c = *utf8++) != 0))
+        {
+            if ((c & 0xc0) == 0x80)
+                /* Valid continuation character. */
+                code = (code << 6) | (c & 0x3f);
+            else
+            {
+                /* Invalid continuation char */
+                code = 0xfffd;
+                utf8--;
+                break;
+            }
+        }
+    }
+    else
+        /* Invalid UTF-8 char */
+        code = 0xfffd;
+
+    /* currently we don't support chars above U-FFFF */
+    *ucs = (code < 0x10000) ? code : 0xfffd;
+    return utf8;
+}
diff --git a/apps/plugins/wikiviewer/shared/utf8_aux.h b/apps/plugins/wikiviewer/shared/utf8_aux.h
new file mode 100644
index 0000000..4e14c54
--- /dev/null
+++ b/apps/plugins/wikiviewer/shared/utf8_aux.h
@@ -0,0 +1,30 @@
+/***************************************************************************
+ *             __________               __   ___.
+ *   Open      \______   \ ____   ____ |  | _\_ |__   _______  ___
+ *   Source     |       _//  _ \_/ ___\|  |/ /| __ \ /  _ \  \/  /
+ *   Jukebox    |    |   (  <_> )  \___|    < | \_\ (  <_> > <  <
+ *   Firmware   |____|_  /\____/ \___  >__|_ \|___  /\____/__/\_ \
+ *                     \/            \/     \/    \/            \/
+ * $Id$
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY
+ * KIND, either express or implied.
+ *
+ ****************************************************************************/
+
+#ifndef __UTF8_AUX_H_
+#define __UTF8_AUX_H_
+
+#include <stdint.h>
+#include <stdbool.h>
+
+const unsigned char* utf8decode(const unsigned char *utf8, unsigned short *ucs);
+char utf8strcnmp(const unsigned char *s1, const unsigned char *s2, uint16_t n1,
+                 uint16_t n2, const bool casesense);
+
+#endif /* __UTF8_AUX_H_ */