base85: Two tiny fixes

base85: Two tiny fixes

[Andreas Gruenbacher]

While looking at the base85 code I found a bug in the debug code and an 
unnecessary call.  You may want to have a look at the two fixes here:

  http://www.kernel.org/pub/scm/linux/kernel/git/agruen/git.git

There is another little oddity in the way the de85 table is set up: 0 
indicates an invalid entry; to avoid this from clashing with a valid entry, 
valid entries are incremented by one and decremented again while decoding.  
This leads to slightly worse code than using a negative number to indicate 
invalid values (and avoiding to increment/decrement).

Andreas

Re: base85: Two tiny fixes

[Nicolas Pitre]

On Thu, 7 Jan 2010, Andreas Gruenbacher wrote:

> While looking at the base85 code I found a bug in the debug code and an 
> unnecessary call.  You may want to have a look at the two fixes here:
> 
>   http://www.kernel.org/pub/scm/linux/kernel/git/agruen/git.git

ACK.  Please post them to this list.

> There is another little oddity in the way the de85 table is set up: 0 
> indicates an invalid entry; to avoid this from clashing with a valid entry, 
> valid entries are incremented by one and decremented again while decoding.  
> This leads to slightly worse code than using a negative number to indicate 
> invalid values (and avoiding to increment/decrement).

You can make a patch to modify that as well if you wish.  And in that 
case don't forget to make de85 explicitly signed as a char is unsigned 
by default on some platforms.


Nicolas

Re: base85: Two tiny fixes

[Andreas Gruenbacher]

On Thursday 07 January 2010 18:58:01 Nicolas Pitre wrote:
> ACK.  Please post them to this list.

Okay, done.

> On Thu, 7 Jan 2010, Andreas Gruenbacher wrote:
> > There is another little oddity in the way the de85 table is set up: 0 
> > indicates an invalid entry; to avoid this from clashing with a valid entry, 
> > valid entries are incremented by one and decremented again while decoding.  
> > This leads to slightly worse code than using a negative number to indicate 
> > invalid values (and avoiding to increment/decrement).
> 
> You can make a patch to modify that as well if you wish.

Nah, it's not worth the noise.

> And in that case don't forget to make de85 explicitly signed as a char is
> unsigned by default on some platforms.

I would have forgotten this; thanks for pointing it out!

Thanks,
Andreas

[PATCH 1/3] base85 debug code: Fix length byte calculation

[Andreas Gruenbacher]

Signed-off-by: Andreas Gruenbacher <agruen@suse.de>
---
 base85.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/base85.c b/base85.c
index b417a15..1d165d9 100644
--- a/base85.c
+++ b/base85.c
@@ -118,7 +118,7 @@ int main(int ac, char **av)
 		int len = strlen(av[2]);
 		encode_85(buf, av[2], len);
 		if (len <= 26) len = len + 'A' - 1;
-		else len = len + 'a' - 26 + 1;
+		else len = len + 'a' - 26 - 1;
 		printf("encoded: %c%s\n", len, buf);
 		return 0;
 	}
-- 
1.6.6.75.g37bae

[PATCH 2/3] base85: No need to initialize the decode table in encode_85

[Andreas Gruenbacher]

Signed-off-by: Andreas Gruenbacher <agruen@suse.de>
---
 base85.c |    2 --
 1 files changed, 0 insertions(+), 2 deletions(-)

diff --git a/base85.c b/base85.c
index 1d165d9..7204ce2 100644
--- a/base85.c
+++ b/base85.c
@@ -84,8 +84,6 @@ int decode_85(char *dst, const char *buffer, int len)
 
 void encode_85(char *buf, const unsigned char *data, int bytes)
 {
-	prep_base85();
-
 	say("encode 85");
 	while (bytes) {
 		unsigned acc = 0;
-- 
1.6.6.75.g37bae

[PATCH 3/3] base85: Make the code more obvious instead of explaining the non-obvious

[Andreas Gruenbacher]

Here is another cleanup ...

Signed-off-by: Andreas Gruenbacher <agruen@suse.de>
---
 base85.c |   10 ++--------
 1 files changed, 2 insertions(+), 8 deletions(-)

diff --git a/base85.c b/base85.c
index 7204ce2..e459fee 100644
--- a/base85.c
+++ b/base85.c
@@ -57,14 +57,8 @@ int decode_85(char *dst, const char *buffer, int len)
 		de = de85[ch];
 		if (--de < 0)
 			return error("invalid base85 alphabet %c", ch);
-		/*
-		 * Detect overflow.  The largest
-		 * 5-letter possible is "|NsC0" to
-		 * encode 0xffffffff, and "|NsC" gives
-		 * 0x03030303 at this point (i.e.
-		 * 0xffffffff = 0x03030303 * 85).
-		 */
-		if (0x03030303 < acc ||
+		/* Detect overflow. */
+		if (0xffffffff / 85 < acc ||
 		    0xffffffff - de < (acc *= 85))
 			return error("invalid base85 sequence %.5s", buffer-5);
 		acc += de;
-- 
1.6.6.75.g37bae

Re: [PATCH 2/3] base85: No need to initialize the decode table in encode_85

[Michael J Gruber]

Andreas Gruenbacher venit, vidit, dixit 08.01.2010 14:39:
> Signed-off-by: Andreas Gruenbacher <agruen@suse.de>
> ---

For the less informed it may be worthwhile to have an explanation in the
commit message why encode_85() does not need to initialize the table. (I
strongly suspect it's a matter of de vs. en, i.e. "because it only
encodes but does not decode."...)

>  base85.c |    2 --
>  1 files changed, 0 insertions(+), 2 deletions(-)
> 
> diff --git a/base85.c b/base85.c
> index 1d165d9..7204ce2 100644
> --- a/base85.c
> +++ b/base85.c
> @@ -84,8 +84,6 @@ int decode_85(char *dst, const char *buffer, int len)
>  
>  void encode_85(char *buf, const unsigned char *data, int bytes)
>  {
> -	prep_base85();
> -
>  	say("encode 85");
>  	while (bytes) {
>  		unsigned acc = 0;

Re: [PATCH 2/3] base85: No need to initialize the decode table in encode_85

[Junio C Hamano]

Michael J Gruber <git@drmicha.warpmail.net> writes:

> Andreas Gruenbacher venit, vidit, dixit 08.01.2010 14:39:
>> Signed-off-by: Andreas Gruenbacher <agruen@suse.de>
>> ---
>
> For the less informed it may be worthwhile to have an explanation in the
> commit message why encode_85() does not need to initialize the table. (I
> strongly suspect it's a matter of de vs. en, i.e. "because it only
> encodes but does not decode."...)

The title can be reworded to

    base85: encode85() does not use the decode table

[PATCH] base85: encode85() does not use the decode table

[Andreas Gruenbacher]

Signed-off-by: Andreas Gruenbacher <agruen@suse.de>
---
 base85.c |    2 --
 1 files changed, 0 insertions(+), 2 deletions(-)

diff --git a/base85.c b/base85.c
index 1d165d9..7204ce2 100644
--- a/base85.c
+++ b/base85.c
@@ -84,8 +84,6 @@ int decode_85(char *dst, const char *buffer, int len)
 
 void encode_85(char *buf, const unsigned char *data, int bytes)
 {
-	prep_base85();
-
 	say("encode 85");
 	while (bytes) {
 		unsigned acc = 0;
-- 
1.6.6.75.g37bae

[PATCH] base85: encode_85() does not use the decode table

[Andreas Gruenbacher]

Signed-off-by: Andreas Gruenbacher <agruen@suse.de>
---
 base85.c |    2 --
 1 files changed, 0 insertions(+), 2 deletions(-)

diff --git a/base85.c b/base85.c
index 1d165d9..7204ce2 100644
--- a/base85.c
+++ b/base85.c
@@ -84,8 +84,6 @@ int decode_85(char *dst, const char *buffer, int len)
 
 void encode_85(char *buf, const unsigned char *data, int bytes)
 {
-	prep_base85();
-
 	say("encode 85");
 	while (bytes) {
 		unsigned acc = 0;
-- 
1.6.6.75.g37bae

Re: [PATCH 3/3] base85: Make the code more obvious instead of explaining the non-obvious

[A Large Angry SCM]

Andreas Gruenbacher wrote:
> Here is another cleanup ...
> 

I LOVE the subject line of this commit!