Perhitungan panjang Base64?

Setelah membaca wiki base64 ...

Saya mencoba mencari tahu bagaimana rumusnya bekerja:

Diberikan string dengan panjang n, panjang base64 akan menjadi

Yang mana : 4*Math.Ceiling(((double)s.Length/3)))

Saya sudah tahu bahwa panjang base64 harus %4==0memungkinkan decoder mengetahui berapa panjang teks aslinya.

Jumlah maksimal padding untuk urutan dapat =atau ==.

wiki: Jumlah byte keluaran per byte input sekitar 4/3 (33% overhead)

Pertanyaan:

Bagaimana informasi di atas sesuai dengan panjang output ?

Setiap karakter digunakan untuk mewakili 6 bit ( log2(64) = 6).

Oleh karena itu 4 karakter digunakan untuk mewakili 4 * 6 = 24 bits = 3 bytes.

Jadi Anda perlu 4*(n/3)karakter untuk mewakili nbyte, dan ini harus dibulatkan menjadi kelipatan 4.

Jumlah karakter pengisi yang tidak digunakan yang dihasilkan dari pembulatan hingga kelipatan 4 jelas akan menjadi 0, 1, 2 atau 3.

4 * n / 3 memberikan panjang yang tidak ditambahkan.

Dan dibulatkan ke kelipatan 4 terdekat untuk padding, dan karena 4 adalah kekuatan 2 dapat menggunakan operasi logis bitwise.

((4 * n / 3) + 3) & ~3

Untuk referensi, rumus panjang encoder Base64 adalah sebagai berikut:

Seperti yang Anda katakan, encoder Base64 yang diberikan nbyte data akan menghasilkan serangkaian 4n/3karakter Base64. Dengan kata lain, setiap 3 byte data akan menghasilkan 4 karakter Base64. EDIT : Sebuah komentar dengan benar menunjukkan bahwa gambar saya sebelumnya tidak menjelaskan padding; rumus yang benar adalah Ceiling(4n/3) .

Artikel Wikipedia menunjukkan dengan tepat bagaimana string ASCII Man dikodekan ke dalam string Base64 TWFudalam contohnya. Input string adalah 3 byte, atau 24 bit, ukuran, sehingga rumus dengan benar memprediksi output akan 4 bytes (atau 32 bit) panjang: TWFu. Proses mengkodekan setiap 6 bit data menjadi salah satu dari 64 karakter Base64, sehingga input 24 bit dibagi dengan 6 hasil dalam 4 karakter Base64.

Anda bertanya dalam komentar berapa ukuran pengkodean 123456. Ingatlah bahwa setiap karakter dari string tersebut berukuran 1 byte, atau 8 bit (dengan asumsi pengkodean ASCII / UTF8), kami menyandikan 6 byte, atau 48 bit, data. Menurut persamaan, kami berharap panjang output menjadi (6 bytes / 3 bytes) * 4 characters = 8 characters.

Menempatkan 123456ke dalam encoder Base64 menciptakan MTIzNDU2, yang panjangnya 8 karakter, seperti yang kita harapkan.

Integer

Umumnya kami tidak ingin menggunakan ganda karena kami tidak ingin menggunakan operasi floating point, pembulatan kesalahan, dll. Mereka tidak perlu.

Untuk ini adalah ide yang baik untuk mengingat bagaimana melakukan pembagian plafon: ceil(x / y)dalam ganda dapat ditulis sebagai (x + y - 1) / y(sambil menghindari angka negatif, tetapi waspadalah terhadap melimpah).

Dapat dibaca

Jika Anda menggunakan keterbacaan, tentu saja Anda juga dapat memprogramnya seperti ini (misalnya dalam Java, untuk C Anda dapat menggunakan makro, tentu saja):

public static int ceilDiv(int x, int y) {
    return (x + y - 1) / y;
}

public static int paddedBase64(int n) {
    int blocks = ceilDiv(n, 3);
    return blocks * 4;
}

public static int unpaddedBase64(int n) {
    int bits = 8 * n;
    return ceilDiv(bits, 6);
}

// test only
public static void main(String[] args) {
    for (int n = 0; n < 21; n++) {
        System.out.println("Base 64 padded: " + paddedBase64(n));
        System.out.println("Base 64 unpadded: " + unpaddedBase64(n));
    }
}

Sebaris

Empuk

Kita tahu bahwa kita membutuhkan 4 blok karakter pada saat itu untuk masing-masing 3 byte (atau kurang). Jadi rumusnya menjadi (untuk x = n dan y = 3):

blocks = (bytes + 3 - 1) / 3
chars = blocks * 4

atau digabungkan:

chars = ((bytes + 3 - 1) / 3) * 4

kompiler Anda akan mengoptimalkan 3 - 1, jadi biarkan saja seperti ini untuk menjaga keterbacaan.

Belum dicetak

Yang kurang umum adalah varian tidak murni, untuk ini kita ingat bahwa setiap kita memerlukan karakter untuk setiap 6 bit, dibulatkan ke atas:

bits = bytes * 8
chars = (bits + 6 - 1) / 6

atau digabungkan:

chars = (bytes * 8 + 6 - 1) / 6

namun kita masih dapat membaginya menjadi dua (jika kita mau):

chars = (bytes * 4 + 3 - 1) / 3

Tidak dapat dibaca

Jika Anda tidak percaya kompiler Anda untuk melakukan optimasi akhir untuk Anda (atau jika Anda ingin membingungkan kolega Anda):

Empuk

((n + 2) / 3) << 2

Belum dicetak

((n << 2) | 2) / 3

Jadi di sinilah kita, dua cara perhitungan logis, dan kita tidak memerlukan cabang, bit-ops atau modulo ops - kecuali kita benar-benar menginginkannya.

Catatan:

• Jelas Anda mungkin perlu menambahkan 1 ke perhitungan untuk memasukkan byte terminasi nol.
• Untuk Mime Anda mungkin perlu mengurus kemungkinan karakter pemutusan baris dan semacamnya (cari jawaban lain untuk itu).

Saya pikir jawaban yang diberikan melewatkan titik pertanyaan awal, yaitu berapa banyak ruang yang perlu dialokasikan agar sesuai dengan pengkodean base64 untuk string biner panjang n byte yang diberikan.

Jawabannya adalah (floor(n / 3) + 1) * 4 + 1

Ini termasuk padding dan penghentian karakter nol. Anda mungkin tidak memerlukan panggilan lantai jika Anda melakukan aritmatika integer.

Termasuk padding, string base64 membutuhkan empat byte untuk setiap potongan tiga byte dari string asli, termasuk potongan parsial. Satu atau dua byte tambahan pada akhir string masih akan dikonversi menjadi empat byte dalam string base64 ketika padding ditambahkan. Kecuali jika Anda memiliki penggunaan yang sangat spesifik, yang terbaik adalah menambahkan padding, biasanya karakter sama dengan. Saya menambahkan byte ekstra untuk karakter nol di C, karena string ASCII tanpa ini sedikit berbahaya dan Anda harus membawa panjang string secara terpisah.

Berikut adalah fungsi untuk menghitung ukuran asli file Base 64 yang dikodekan sebagai String dalam KB:

private Double calcBase64SizeInKBytes(String base64String) {
    Double result = -1.0;
    if(StringUtils.isNotEmpty(base64String)) {
        Integer padding = 0;
        if(base64String.endsWith("==")) {
            padding = 2;
        }
        else {
            if (base64String.endsWith("=")) padding = 1;
        }
        result = (Math.ceil(base64String.length() / 4) * 3 ) - padding;
    }
    return result / 1000;
}

Sementara semua orang berdebat rumus aljabar, saya lebih suka menggunakan BASE64 sendiri untuk memberi tahu saya:

$ echo "Including padding, a base64 string requires four bytes for every three-byte chunk of the original string, including any partial chunks. One or two bytes extra at the end of the string will still get converted to four bytes in the base64 string when padding is added. Unless you have a very specific use, it is best to add the padding, usually an equals character. I added an extra byte for a null character in C, because ASCII strings without this are a little dangerous and you'd need to carry the string length separately."| wc -c

525

$ echo "Including padding, a base64 string requires four bytes for every three-byte chunk of the original string, including any partial chunks. One or two bytes extra at the end of the string will still get converted to four bytes in the base64 string when padding is added. Unless you have a very specific use, it is best to add the padding, usually an equals character. I added an extra byte for a null character in C, because ASCII strings without this are a little dangerous and you'd need to carry the string length separately." | base64 | wc -c

710

Jadi sepertinya rumus 3 byte yang diwakili oleh 4 karakter base64 tampaknya benar.

(Dalam upaya untuk memberikan derivasi yang ringkas namun lengkap.)

Setiap byte input memiliki 8 bit, jadi untuk n byte input kita dapatkan:

n × 8 bit input

Setiap 6 bit adalah byte keluaran, jadi:

ceil ( n × 8/6 ) =  keluaran keluaran ceil ( n × 4/3 )

Ini tanpa bantalan.

Dengan bantalan, kami membulatkannya hingga beberapa dari empat byte keluaran:

ceil ( ceil ( n × 4/3 ) / 4) × 4 =  ceil ( n × 4/3/4 ) × 4 =  ceil ( n / 3) × 4 byte keluaran

Lihat Divisi Bertingkat (Wikipedia) untuk kesetaraan pertama.

Menggunakan integer arithmetics, ceil ( n / m ) dapat dihitung sebagai ( n + m - 1) div m , maka kita mendapatkan:

( n * 4 + 2) div 3 tanpa bantalan

( n + 2) div 3 * 4 dengan bantalan

Untuk ilustrasi:

 n   with padding    (n + 2) div 3 * 4    without padding   (n * 4 + 2) div 3 
------------------------------------------------------------------------------
 0                           0                                      0
 1   AA==                    4            AA                        2
 2   AAA=                    4            AAA                       3
 3   AAAA                    4            AAAA                      4
 4   AAAAAA==                8            AAAAAA                    6
 5   AAAAAAA=                8            AAAAAAA                   7
 6   AAAAAAAA                8            AAAAAAAA                  8
 7   AAAAAAAAAA==           12            AAAAAAAAAA               10
 8   AAAAAAAAAAA=           12            AAAAAAAAAAA              11
 9   AAAAAAAAAAAA           12            AAAAAAAAAAAA             12
10   AAAAAAAAAAAAAA==       16            AAAAAAAAAAAAAA           14
11   AAAAAAAAAAAAAAA=       16            AAAAAAAAAAAAAAA          15
12   AAAAAAAAAAAAAAAA       16            AAAAAAAAAAAAAAAA         16

Akhirnya, dalam kasus pengkodean MIME Base64, dua byte tambahan (CR LF) diperlukan per setiap 76 byte output, dibulatkan ke atas atau ke bawah tergantung pada apakah diperlukan baris baru yang mengakhiri.

Menurut saya formula yang tepat adalah:

n64 = 4 * (n / 3) + (n % 3 != 0 ? 4 : 0)

Saya percaya bahwa ini adalah jawaban yang tepat jika n% 3 bukan nol, bukan?

    (n + 3-n%3)
4 * ---------
       3

Versi Mathematica:

SizeB64[n_] := If[Mod[n, 3] == 0, 4 n/3, 4 (n + 3 - Mod[n, 3])/3]

Selamat bersenang-senang

GI

Implementasi sederhana dalam javascript

function sizeOfBase64String(base64String) {
    if (!base64String) return 0;
    const padding = (base64String.match(/(=*)$/) || [])[1].length;
    return 4 * Math.ceil((base64String.length / 3)) - padding;
}

Untuk semua orang yang berbicara C, lihat dua makro ini:

// calculate the size of 'output' buffer required for a 'input' buffer of length x during Base64 encoding operation
#define B64ENCODE_OUT_SAFESIZE(x) ((((x) + 3 - 1)/3) * 4 + 1) 

// calculate the size of 'output' buffer required for a 'input' buffer of length x during Base64 decoding operation
#define B64DECODE_OUT_SAFESIZE(x) (((x)*3)/4) 

Diambil dari sini .

Saya tidak melihat rumus yang disederhanakan dalam tanggapan lain. Logikanya tercakup tetapi saya menginginkan bentuk paling dasar untuk penggunaan yang disematkan:

  Unpadded = ((4 * n) + 2) / 3

  Padded = 4 * ((n + 2) / 3)

CATATAN: Saat menghitung jumlah yang tidak ditambahkan, kami mengumpulkan divisi bilangan bulat yaitu menambahkan Divisor-1 yang merupakan +2 dalam kasus ini

Di windows - Saya ingin memperkirakan ukuran buffer berukuran mime64, tetapi semua rumus perhitungan yang tepat tidak bekerja untuk saya - akhirnya saya berakhir dengan rumus perkiraan seperti ini:

Ukuran alokasi string Mine64 (perkiraan) = (((4 * ((ukuran buffer biner) + 1)) / 3) + 1)

Jadi +1 terakhir - digunakan untuk ascii-nol - karakter terakhir perlu dialokasikan untuk menyimpan akhiran nol - tetapi mengapa "ukuran buffer biner" adalah +1 - Saya menduga ada beberapa karakter terminasi mime64? Atau mungkin ini masalah pelurusan.

Jika ada seseorang yang tertarik untuk mencapai solusi @Pedro Silva di JS, saya baru saja mem-porting solusi yang sama untuk ini:

const getBase64Size = (base64) => {
  let padding = base64.length
    ? getBase64Padding(base64)
    : 0
  return ((Math.ceil(base64.length / 4) * 3 ) - padding) / 1000
}

const getBase64Padding = (base64) => {
  return endsWith(base64, '==')
    ? 2
    : 1
}

const endsWith = (str, end) => {
  let charsFromEnd = end.length
  let extractedEnd = str.slice(-charsFromEnd)
  return extractedEnd === end
}