From b93c820d808e85854568f479c30904aeaf453459 Mon Sep 17 00:00:00 2001 From: girst Date: Thu, 10 Nov 2016 02:58:15 +0100 Subject: [PATCH 1/1] First version --- Makefile | 15 +++++ README.md | 43 ++++++++++++++ main.c | 171 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 229 insertions(+) create mode 100644 Makefile create mode 100644 README.md create mode 100644 main.c diff --git a/Makefile b/Makefile new file mode 100644 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 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 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 +#include +#include +#include +#include +#include + +#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< 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; +} -- 2.39.3