string - बेस 64 लंबाई गणना?




base64 padding (7)

बेस 64 wiki पढ़ने के बाद ...

मैं यह जानने की कोशिश कर रहा हूं कि फॉर्मूला कैसे काम कर रहा है:

n लंबाई के साथ एक स्ट्रिंग को देखते हुए, बेस 64 लंबाई होगी

जो है: 4*Math.Ceiling(((double)s.Length/3)))

मुझे पहले से ही पता है कि डीकोडर को मूल टेक्स्ट लंबाई क्या है, इसकी अनुमति देने के लिए बेस 64 लंबाई %4==0 होना चाहिए।

अनुक्रम के लिए पैडिंग की अधिकतम संख्या = या == हो सकती है।

विकी: प्रति इनपुट बाइट आउटपुट बाइट्स की संख्या लगभग 4/3 (33% ओवरहेड) है

सवाल:

उपरोक्त जानकारी आउटपुट लंबाई के साथ कैसे व्यवस्थित होती है ?


पूर्णांकों

आम तौर पर हम युगल का उपयोग नहीं करना चाहते हैं क्योंकि हम फ्लोटिंग पॉइंट ऑप्स, गोलाकार त्रुटियों आदि का उपयोग नहीं करना चाहते हैं। वे केवल जरूरी नहीं हैं।

इसके लिए यह याद रखना एक अच्छा विचार है कि छत विभाजन कैसे करें: युगल में छत ceil(x / y) को (x + y - 1) / y (नकारात्मक संख्याओं से परहेज करते हुए, लेकिन अतिप्रवाह से सावधान रहना) के रूप में लिखा जा सकता है।

पठनीय

यदि आप पठनीयता के लिए जाते हैं तो आप निश्चित रूप से इसे इस तरह प्रोग्राम भी कर सकते हैं (जावा में उदाहरण, सी के लिए आप मैक्रो का उपयोग कर सकते हैं):

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));
    }
}

inlined

गुदगुदा

हम जानते हैं कि प्रत्येक 3 बाइट (या कम) के लिए हमें उस समय 4 वर्ण ब्लॉक की आवश्यकता होती है। तो फिर सूत्र बन जाता है (x = n और y = 3 के लिए):

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

या संयुक्त:

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

आपका कंपाइलर 3 - 1 को अनुकूलित करेगा, इसलिए इसे पठनीयता बनाए रखने के लिए इसे इस तरह छोड़ दें।

unpadded

कम आम है अनपढ़ संस्करण, इसके लिए हम याद करते हैं कि प्रत्येक को प्रत्येक 6 बिट्स के लिए एक चरित्र की आवश्यकता होती है, गोलाकार:

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

या संयुक्त:

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

हालांकि हम अभी भी दो से विभाजित कर सकते हैं (अगर हम चाहते हैं):

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

अस्पष्ट

यदि आप अपने कंपाइलर पर आपके लिए अंतिम अनुकूलन करने पर भरोसा नहीं करते हैं (या यदि आप अपने सहयोगियों को भ्रमित करना चाहते हैं):

गुदगुदा

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

unpadded

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

तो हम गणना के दो तार्किक तरीके हैं, और हमें किसी भी शाखा, बिट-ऑप्स या मॉड्यूलो ऑप्स की आवश्यकता नहीं है - जब तक हम वास्तव में नहीं चाहते हैं।

टिप्पणियाँ:

  • जाहिर है, आपको नल टर्मिनेशन बाइट शामिल करने के लिए गणनाओं में 1 जोड़ना पड़ सकता है।
  • माइम के लिए आपको संभावित लाइन समाप्ति पात्रों का ख्याल रखना पड़ सकता है और ऐसे (इसके लिए अन्य उत्तरों की तलाश करें)।

केबी में एक स्ट्रिंग के रूप में एन्कोडेड बेस 64 फ़ाइल के मूल आकार की गणना करने के लिए यहां एक फ़ंक्शन है:

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;
}

प्रत्येक चरित्र का उपयोग 6 बिट्स ( log2(64) = 6 ) का प्रतिनिधित्व करने के लिए किया जाता है।

इसलिए 4 वर्णों का उपयोग 4 * 6 = 24 bits = 3 bytes का प्रतिनिधित्व करने के लिए किया जाता है।

तो आपको n बाइट्स का प्रतिनिधित्व करने के लिए 4*(n/3) वर्णों की आवश्यकता है, और इसे 4 में से एक के लिए गोलाकार करने की आवश्यकता है।

4 से अधिक के राउंडिंग के परिणामस्वरूप अप्रयुक्त पैडिंग वर्णों की संख्या स्पष्ट रूप से 0, 1, 2 या 3 होगी।


मुझे लगता है कि दिए गए उत्तरों मूल प्रश्न के बिंदु को याद करते हैं, जो लंबाई एन बाइट्स की दी गई बाइनरी स्ट्रिंग के लिए बेस 64 एन्कोडिंग को फिट करने के लिए कितनी जगह आवंटित करने की आवश्यकता है।

जवाब है (floor(n / 3) + 1) * 4 + 1

इसमें पैडिंग और टर्मिनिंग नल कैरेक्टर शामिल है। यदि आप पूर्णांक अंकगणित कर रहे हैं तो आपको फर्श कॉल की आवश्यकता नहीं हो सकती है।

पैडिंग सहित, बेस 64 स्ट्रिंग को मूल स्ट्रिंग के प्रत्येक तीन-बाइट खंड के लिए चार बाइट की आवश्यकता होती है, जिसमें किसी भी आंशिक भाग शामिल हैं। स्ट्रिंग के अंत में अतिरिक्त एक या दो बाइट अभी भी बेस 64 स्ट्रिंग में चार बाइट्स में परिवर्तित हो जाएंगे जब पैडिंग जोड़ा जाता है। जब तक आपके पास एक बहुत ही विशिष्ट उपयोग न हो, तब तक पैडिंग को जोड़ना सबसे अच्छा होता है, आमतौर पर एक बराबर चरित्र होता है। मैंने सी में एक शून्य चरित्र के लिए एक अतिरिक्त बाइट जोड़ा, क्योंकि इसके बिना एएससीआईआई स्ट्रिंग थोड़ा खतरनाक है और आपको स्ट्रिंग लम्बाई अलग से ले जाने की आवश्यकता होगी।


मेरा मानना ​​है कि यह एक सही जवाब है यदि एन% 3 शून्य नहीं है, नहीं?

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

गणित संस्करण:

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

मज़े करो

सैनिक


विंडोज़ में - मैं mime64 आकार के बफर के आकार का आकलन करना चाहता था, लेकिन सभी सटीक गणना फॉर्मूला मेरे लिए काम नहीं करता था - अंत में मैं इस तरह के अनुमानित सूत्र के साथ समाप्त हुआ हूं:

Mine64 स्ट्रिंग आवंटन आकार (अनुमानित) = (((4 * ((बाइनरी बफर आकार) + 1)) / 3) + 1)

तो आखिरी +1 - इसका उपयोग एसीआईआई-शून्य के लिए किया जाता है - अंतिम चरित्र को शून्य अंतराल को स्टोर करने के लिए आवंटित करने की आवश्यकता होती है - लेकिन क्यों "बाइनरी बफर आकार" + 1 है - मुझे संदेह है कि कुछ माइम 64 समाप्ति चरित्र है? या यह कुछ संरेखण मुद्दा हो सकता है।


4 * n / 3 अनपढ़ लंबाई देता है।

और पैडिंग के लिए 4 के निकटतम एकाधिक तक पहुंचें, और 4 की शक्ति 2 बिटवाई लॉजिकल ऑपरेशंस का उपयोग कर सकती है।

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




formula