Subject: base64 byte-length formula

From: Martins Krikis <[email-masked]>
Date: Wed, 12 Jun 2002 14:01:21 -0700 (PDT)

I don't particularly care, but the formula given
on page 71 of 12-98 is wrong (and I've mentioned
it a few times already).

A very simple counterexample:

0 base64 digits should result in a 0-byte binary
string. According to the given formula, 
floor((0 + 3) * 3 / 4) - 0) = 2.

Another, more realistic but just as simple one:

4 base64 digits should result in a 3-byte binary
string. According to the given formula,
floor((4 + 3) * 3 / 4) - 0) = 5.

The given formula also fails for n = 3 (mod 4).

The correct formula, IMO is the following:
floor(n * 3 / 4).

In other words, there is no need to even count
the equivalence signs at the end, nor to add
any constants.

Martins Krikis, Intel Corp.

Disclaimer: these opinions are mine and may
            not be my employer's.

__________________________________________________
Do You Yahoo!?
Yahoo! - Official partner of 2002 FIFA World Cup
http://fifaworldcup.yahoo.com

---

From: "Julian Satran" <[email-masked]>
Date: Thu, 13 Jun 2002 01:02:56 +0300

Sorry - It must have stayed in my pile. Your formula is not correct.
The correct one is (n*3 + 3)/4

Julo

Martins Krikis <[email-masked]>
Sent by: [email-masked]
06/13/2002 12:01 AM
Please respond to Martins Krikis

        To:     [email-masked]
        cc: 
        Subject:        base64 byte-length formula

---

From: Martins Krikis <[email-masked]>
Date: Wed, 12 Jun 2002 15:56:28 -0700 (PDT)

Sorry, I had missed to CC the previous to the list
but I'm doing it with this. The way you understand
base64 is not the way I understand it. Can somebody
please chime in and set the record straight?

Here is the relevant text from RFC 2045, describing
the base64 encoding process. We are, of course,
talking about decoding in these length-calculation
formulas. More of my comments further down in text.

<RFC 2045 QUOTE>
  Special processing is performed if fewer 
  than 24 bits are available
  at the end of the data being encoded.  
  A full encoding quantum is
  always completed at the end of a body.  
  When fewer than 24 input bits
  are available in an input group, zero 
  bits are added (on the right)
  to form an integral number of 6-bit groups.  
  Padding at the end of
  the data is performed using the "=" character.
  Since all base64
  input is an integral number of octets, 
  only the following cases can
  arise: (1) the final quantum of encoding 
  input is an integral
  multiple of 24 bits; here, the final 
  unit of encoded output will be
  an integral multiple of 4 characters 
  with no "=" padding, (2) the
  final quantum of encoding input is 
  exactly 8 bits; here, the final
  unit of encoded output will be two 
  characters followed by two "="
  padding characters, or (3) the final 
  quantum of encoding input is
  exactly 16 bits; here, the final 
  unit of encoded output will be three
  characters followed by one "=" padding 
  character.
</RFC 2045 QUOTE>

--- Julian Satran <[email-masked]> wrote:

> comments in text - julo
> 
> --- Julian Satran <[email-masked]> wrote:
> 
> > Sorry - It must have stayed in my pile. Your
> formula
> > is not correct.
> Do you have any counterexamples to my formula?
> 
> +++ 1 b64 digit is one byte - according to you it is
> 0 +++

1 b64 digit is impossible. It would need 3 '='s
at the end and such a case is not mentioned in
the RFC. It would not describe a full byte either.

> Here are a couple for yours (unless I'm totally
> messed up and don't know how base64 encoding works):
> 
> 3 base64 digits with 1 equivalence sign at the
> end should result in a 2-byte binary string.
> According to your new formula:
> (3 * 3 + 3) / 4 = 3.
> 
> +++ 3 b64 digits (18 bits) are 3 bytes +++

No, it's case (3) in the quote from RFC I made
above, these 18 bits describe 2 full bytes,
not 3 incomplete ones. 

> 2 base64 digits with 2 equivalence signs at the
> end should result in a 1-byte binary string.
> According to your new formula:
> (2 * 3 + 3) / 4 = 2.
> 
> +++ incorrect - 2 digits is 12 bit is 2 bytes +++

No, it's case (2) in the quote from RFC I made
above, these 12 bits describe 1 full byte, not
2 incomplete ones.

You really have to imagine the encoding process
when thinking about how to decode.

Disclaimer: these opinions are mine and
            may not be my employer's.

---

From: [email-masked]
Date: Wed, 12 Jun 2002 18:33:22 -0600

Julian,

The formula in 12-97 is: 
((the integer part of)((n+3)*3/4) - m)

Martins formula 3*3/4 where / indictates integer divide.

The encoding of 1 octet in base64 results in 2 characters plus 2 equal
signs. 
n=2, m=2.

Martins formula = 2 *3/4 = 1 (truncated to an integer)  right answer

integer part of ((2+3)*3/4)-1 = (integer part of 15/4) - 2 = 3 - 2 = 1 right
answer

The encoding of 2 octets in base64 results in 3 characters plus one equal
sign. 
n=3, m=1.

Martins formula = 3 *3/4 = 2 (truncated to an integer)  right answer

integer part of ((3+3)*3/4)-1 = (integer part of 18/4) -1 = 4 - 1 = 3 wrong
answer

The encoding of 3 octets in base64 results in 4 characters plus no equal
sign. 
n=4, m=0.

Martins formula = 4 *3/4 = 3 (truncated to an integer)  right answer

integer part of ((4+3)*3/4)-1 = (integer part of 21/4) -0 = 5 - 1 = 4 wrong
answer

Pat

-----Original Message-----
From: Julian Satran [mailto:[email-masked]]
Sent: Wednesday, June 12, 2002 4:56 PM
To: Martins Krikis
Cc: [email-masked]; [email-masked]
Subject: Re: base64 byte-length formula

I said already that your formula is correct. 
I do not understand why you say that the 2 formulas are not equivalent for
all the lengths (good aor bad)? 
I would appreciate if you respond although you don't have to. 

Julo 

06/13/2002 02:34 AM 
        
        To:        Julian Satran/Haifa/IBM@IBMIL 
        cc:        [email-masked] 
        Subject:        Re: base64 byte-length formula 

--- Julian Satran <[email-masked]> wrote:

> The difference between our formulas is that I
> (mistakenly) took 1 digit as 
> a possible string (or 5, 9 etc.)
> For those you need the +3 TERM.
> 
> For all the good length 2,3,4 6,7,8 etc the two
> formulas are equivalent.

No they are not. They are only equivalent for
n = 0 (mod 4). So I'm still insisting that
n * 3 / 4 is the simplest right formula.

Disclaimer: these are my opinions and
           may not be Intel's.

---

From: "Julian Satran" <[email-masked]>
Date: Thu, 13 Jun 2002 15:57:03 +0300

Pat,

I think you are talking about the formula in 12-96 and I am talking about 
the one in 12-98.
Martins formula and mine are equivalent for good encodings.
As I said I made it up only to account for encodings that are in fact 
impossible - like 1, 4 ... 4*n+1 base 64 digits.
And I will  put in Martins formula with a note about the impossible 
numbers.
Can we stop this thread?

Julo

[email-masked]
06/13/2002 03:33 AM
Please respond to pat_thaler

        To:     Julian Satran/Haifa/IBM@IBMIL, [email-masked]
        cc:     [email-masked], [email-masked]
        Subject:        RE: base64 byte-length formula

Julian,

The formula in 12-97 is: 

integer part of ((2+3)*3/4)-1 = (integer part of 15/4) - 2 = 3 - 2 = 1 
right
answer

integer part of ((3+3)*3/4)-1 = (integer part of 18/4) -1 = 4 - 1 = 3 
wrong
answer

integer part of ((4+3)*3/4)-1 = (integer part of 21/4) -0 = 5 - 1 = 4 
wrong
answer

Pat

-----Original Message-----
From: Julian Satran [mailto:[email-masked]]
Sent: Wednesday, June 12, 2002 4:56 PM
To: Martins Krikis
Cc: [email-masked]; [email-masked]
Subject: Re: base64 byte-length formula

Julo

---

From: [email-masked]
Date: Thu, 13 Jun 2002 10:33:55 -0600

Julian,
 
I was using the formula in 12-97 as I stated. The formulas on 12-96 page 70,
12-97 page 71 and 12-98 page 71 all look the same to me. Changing to
Martin's formula will solve the problem as would removing the formula
altogether.
 
Regards,
Pat
 
 -----Original Message-----
From: Julian Satran [mailto:[email-masked]]
Sent: Thursday, June 13, 2002 5:57 AM
To: [email-masked]
Cc: [email-masked]; [email-masked]; [email-masked]
Subject: RE: base64 byte-length formula

Pat, 

And I will  put in Martins formula with a note about the impossible numbers.

Can we stop this thread? 

Julo 

	[email-masked] 

06/13/2002 03:33 AM 

Julian,

The formula in 12-97 is: 

Pat

-----Original Message-----
From: Julian Satran [mailto:[email-masked]]
Sent: Wednesday, June 12, 2002 4:56 PM
To: Martins Krikis
Cc: [email-masked]; [email-masked]
Subject: Re: base64 byte-length formula

Julo