First version

diff --git a/Makefile b/Makefile
new file mode 100644 (file)
index 0000000..ed3c71a
--- /dev/null
+++ b/Makefile
@@ -0,0 +1,15 @@
+# base1
+# (C) 2016 Tobias Girstmair, http://isticktoit.net/
+# released under the GNU GPL v3. See LICENSE for details.
+
+.PHONY: all clean test
+CC=gcc
+CFLAGS=-std=c99 -Werror -Wall -Wextra
+
+all: base1
+
+base1:
+       $(CC) $(CFLAGS) main.c -o base1
+
+clean:
+       rm -f base1

diff --git a/README.md b/README.md
new file mode 100644 (file)
index 0000000..b0ec2e1
--- /dev/null
+++ b/README.md
@@ -0,0 +1,43 @@
+# base1
+
+Reimplementation of [ferno][1]'s [`base1`][2] in C for UNIXoid shells. 
+
+## Why
+ * Why not?
+ * guaranteed to be compatible with __any__ character set, no matter how small
+   (theoretically)
+
+## Building
+To generate the binary, run `make`. Then, copy the resulting `base1` binary to
+a directory in your `$PATH`.
+
+## Usage
+`base1` uses GNU's [`base64`][4] tool as a reference and therefore has similar
+command line arguments. This means, you can either pipe data in or give a file
+as an argument. 
+
+The non-standard parameter `-t` will return the length of the string to be
+encoded, or warn if it will overflow. 
+
+### 'Hello World'-Example:
+Can't do: even on 64 bit machines the length of the resulting string will be
+larger than `unsigned long long int`. I en- and decoded the string `Hallo` - it
+took 52 **minutes**!
+
+    echo -n "Hi" | ./base1 -w 0
+
+will output 18794 `A`s.
+
+## License
+`base1` is released under the GNU General Public License, version 3.    
+See `LICENSE` for details.
+© 2016 Tobias Girstmair, [isticktoit.net][5]
+
+## In other Languages
+ * [JavaScript](https://github.com/ferno/base1)
+
+[1]: https://github.com/ferno/
+[2]: https://github.com/ferno/base1
+[3]: https://twitter.com/girstmair
+[4]: http://linux.die.net/man/1/base64
+[5]: http://isticktoit.net/

diff --git a/main.c b/main.c
new file mode 100644 (file)
index 0000000..0c57be3
--- /dev/null
+++ b/main.c
@@ -0,0 +1,171 @@
+/* base1 en- and decoder with usage similar to GNU's base64.
+(C) 2016 Tobias Girstmair, http://isticktoit.net/
+Released under the GNU GPL v3. See LICENSE for details. */
+
+#define _XOPEN_SOURCE
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+#include <limits.h>
+#include <stdint.h>
+
+#define VERSION "0.1"
+
+#define DEFAULT_WRAP 72
+
+#define COPYRIGHT "(C) 2016 Tobias Girstmair, GPLv3"
+#define HELP_TEXT \
+       "Usage: %s [OPTION]... [FILE]\n"\
+       "Options: -d (decode), -i (ignore-garbage), -w COLS (wrap, default %d)"\
+       " -t (test) -v (version) -h (help)\n"
+
+#define BASE ((1<<CHAR_BIT)) //2 ^ (bits of a byte)
+
+struct ops {
+       FILE* f;
+       int d; /*decode*/
+       int i; /*ignore-garbage*/
+       int w; /*wrap*/
+       int t; /*test*/
+};
+
+size_t highestOneBitPosition(unsigned long long a);
+int multiplication_is_safe(unsigned long long a, unsigned long long b);
+int addition_is_safe(unsigned long long a, unsigned long long b);
+
+void do_encode (FILE* in, FILE* out, int wrap_column, int test_only);
+void do_decode (FILE* in, FILE* out, int ignore_garbage);
+
+
+int main (int argc, char** argv) {
+       struct ops op = {stdin, 0, 0, DEFAULT_WRAP, 0};
+       int opt;
+
+       opterr=0; /* suppress default error messages */
+       while ( (opt = getopt(argc, argv, "diw:tvh")) != -1)  {
+               switch (opt) {
+               case 'd': op.d = 1; break;
+               case 'i': op.i = 1; break;
+               case 'w': op.w = atoi (optarg); break;
+               case 't': op.t = 1; break;
+               case 'v':
+                       fprintf (stderr, "base1 %s\n%s\n", VERSION, COPYRIGHT);
+                       return 0;
+               case 'h':
+                       fprintf (stderr, HELP_TEXT, argv[0], DEFAULT_WRAP);
+                       return 0;
+               default:
+                       fprintf (stderr, "unknown option '-%c'.\n", optopt);
+                       return 1;
+               }
+       }
+       if (argc-optind > 1) {
+               fprintf (stderr, "%s: extra operand '%s'. \n", argv[0], argv[argc-1]);
+               return 1;
+       } else if (optind < argc) {
+               if (strcmp (argv [optind], "-") != 0)
+                       op.f = fopen (argv[optind], "rb");
+       }
+
+       if (op.d) {
+               do_decode (op.f, stdout, op.i);
+       } else {
+               do_encode (op.f, stdout, op.w, op.t);
+       }
+
+       if (op.f != stdin) fclose (op.f);
+
+       return 0;
+}
+
+
+
+
+void do_encode (FILE* in, FILE* out, int wrap_column, int test_only) {
+       int in_len = 0;
+       unsigned long long out_len = 0;
+
+       for (int in_char; (in_char = getc(in)) != EOF; in_len++) {
+               if (!multiplication_is_safe (out_len, BASE)){
+                       puts ("overflowed.");
+                       return;
+               }
+               out_len *= BASE;
+               if (!addition_is_safe (out_len, in_char)) {
+                       puts ("overflowed.");
+                       return;
+               }
+               out_len += in_char;
+       }
+
+       if (test_only) {
+               printf ("Length of output:\t%llu\nMaximum value of ULL:\t%llu\n", out_len, ULLONG_MAX);
+               return;
+       }
+
+       unsigned long long block_size = 1;
+
+       for (int i = 0; i < in_len; i++) {
+               out_len += block_size;
+               block_size *= BASE;
+       }
+
+       for (unsigned long long i = 0; i < out_len; i++)
+               fprintf (out, "%s%c", wrap_column&&!(i%wrap_column)&&i?"\n":"", 'A');
+               //TODO: use faster function
+}
+
+void do_decode (FILE* in, FILE* out, int ignore_garbage) {
+       unsigned long long in_len = 0;
+
+       for (int in_char; (in_char = getc (in)) != EOF;) {
+               if (in_char == ' ' || in_char == '\n' || in_char == '\t') {
+                       continue;
+               } else if (in_char == 'A') {
+                       in_len++;
+               } else if (!ignore_garbage) {
+                       fprintf (stderr, "Unrecognized glyph %c\n", in_char);
+                       return;
+               }
+               // TODO: check for overflow!
+       }
+
+       int bin_len = 0;
+       unsigned long long block_size = 1;
+       while (in_len >= block_size) {
+               in_len -= block_size;
+               bin_len++;
+               block_size *= BASE;
+       }
+
+       char b;
+       char out_buf[bin_len];
+       for (int byte_num = bin_len-1; byte_num >= 0; byte_num--) {
+               b = in_len & (BASE - 1);
+               out_buf[byte_num] = b;
+               in_len -= b;
+               in_len /= BASE;
+       }
+
+       for (int i = 0; i < bin_len; i++) putc (out_buf[i], out);
+}
+
+/* http://stackoverflow.com/a/199455 */
+int addition_is_safe(unsigned long long a, unsigned long long b) {
+       size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
+       return (a_bits<64 && b_bits<64);
+}
+
+int multiplication_is_safe(unsigned long long a, unsigned long long b) {
+       size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
+       return (a_bits+b_bits<=64);
+}
+size_t highestOneBitPosition(unsigned long long a) {
+       size_t bits=0;
+       while (a!=0) {
+               ++bits;
+               a>>=1;
+       };
+       return bits;
+}