Bu konu beni de çekti ve gittikçe içine girdim. :) Baştan çok zorlandım ama sonunda üç farklı aralık kullanan bir çözüm buldum.
RFC'de de anlatıldığı gibi, aslında Base32 RandomAccessRange aralıklarıyla çok daha hızlı işlenebilir. Ben yalnızca InputRange gerektiren ve asıl aralığın başındaki iki elemanı gerektikçe kendi ara belleğinde tutan bir aralık yazdım.
Kodda bir sürü denetim eksik; örneğin, bir sürü assert serpiştirilebilir.
Bu çözüm Base32'nin üç işlevini farklı aralıklarla gerçekleştiriyor:
BitParçaları: Veriyi belirtilen genişlikteki parçalar halinde sunuyor. Bu genişlik, Base32 için 5; Base64 için 6. (Base32 dışında denemedim.)
UzunluğuTamBölünen: Asıl aralık kısa bile olsa belirtilen doldurma elemanını kullanarak belirli bir uzunluğa tam olarak bölünen sayıda eleman üretiyor. Bu, Base32 kodlamasının 8'in katları olması gereğini karşılıyor.
Dönüştür: Eleman değerlerini indeks olarak kullanarak belirtilen alfabenin harflerine dönüştürüyor.
Base64'ü denemedim ama bence bu aralıklardan yola çıkıldığında o da çok kolay olacaktır.
Ali
import std.stdio;
import std.array;
import std.range;
import std.traits;
import std.conv;
/**
* Belirtilen türün kaç bitten oluştuğunu bildirir.
*/
size_t toplamBit(T)() @property
{
return T.sizeof * 8;
}
unittest
{
assert(toplamBit!char == 8);
assert(toplamBit!long == 64);
}
/*
* Verinin belirtilen konumdaki bitinden sağa doğru 'adet' adet bitinin
* değerini döndürür.
*
* Veriyi bir bit topluluğu olarak gördüğü için 0 numaralı bit en soldakidir.
*/
T bitÇek(T)(T veri, size_t konum, size_t adet)
if (!isStaticArray!T)
{
veri <<= konum;
veri >>>= toplamBit!T - adet;
return veri;
}
unittest
{
ubyte veri = 0b_1010_1100;
assert(bitÇek(veri, 0, 0) == 0);
assert(bitÇek(veri, 0, 1) == 1);
assert(bitÇek(veri, 0, 2) == 2);
assert(bitÇek(veri, 0, 3) == 5);
assert(bitÇek(veri, 0, 4) == 10);
assert(bitÇek(veri, 0, 5) == 21);
assert(bitÇek(veri, 0, 6) == 43);
assert(bitÇek(veri, 0, 7) == 86);
assert(bitÇek(veri, 0, 8) == 172);
veri = 0b10110101;
assert(bitÇek(veri, 0, 3) == 5);
assert(bitÇek(veri, 1, 3) == 3);
assert(bitÇek(veri, 2, 3) == 6);
assert(bitÇek(veri, 3, 3) == 5);
assert(bitÇek(veri, 4, 3) == 2);
assert(bitÇek(veri, 5, 3) == 5);
}
/*
* Yukarıdaki bitÇek gibi işler ama iki elemanlı sabit dizi kullanır. Çekilen
* bitler her iki eleman üzerinde duruyor olabilir.
*/
E bitÇek(T : E[2], E)(T veri, size_t konum, size_t adet)
if (isStaticArray!T)
{
if ((konum + adet) < toplamBit!E) {
// Hepsi ilk baytın içinde
return bitÇek(veri[0], konum, adet);
} else if (konum >= toplamBit!E) {
// Hepsi ikinci baytın içinde
return bitÇek(veri[1], konum - toplamBit!E, adet);
} else {
// İki baytta da parçası var
immutable ilkBaytBiti = toplamBit!E - konum;
immutable ikinciBaytBiti = adet - ilkBaytBiti;
auto sonuç = ((bitÇek(veri[0], konum, ilkBaytBiti) << ikinciBaytBiti) |
bitÇek(veri[1], 0, ikinciBaytBiti));
// İşlemler int terfileri nedeniyle E'den başka bir türde gerçekleşmiş
// olabilir. Eleman türüne dönüştürmemiz gerekiyor.
return cast(E)sonuç;
}
}
unittest
{
ubyte[2] veri = [ 0b_1011_0101, 0b_1001_0011 ];
assert(bitÇek(veri, 0, 2) == 2);
assert(bitÇek(veri, 2, 3) == 6);
assert(bitÇek(veri, 6, 5) == 12);
assert(bitÇek(veri, 8, 4) == 9);
assert(bitÇek(veri, 11, 5) == 19);
}
/*
* Belirtilen aralığı bir bit topluluğu olarak görür. O bitleri her birisi
* 'parçaGenişliği' genişliğindeki parçalar halinde sunar.
*/
struct BitParçaları(size_t parçaGenişliği, R)
if (isInputRange!R &&
__traits(isUnsigned, ElementType!R) &&
parçaGenişliği <= toplamBit!(ElementType!R))
{
alias E = ElementType!R;
R aralık; // Asıl aralık
Unqual!E[2] araBellek; // Aralığın ilk iki elemanının kopyası
size_t konum; // Bir sonraki okumanın araBellek'in hangi
// konumundan olacağı
int hazırBitler; // araBellek'te kaç bitin hazır olduğu (Eksi
// değer aralığın boş olduğunu belirtir)
Unqual!E front_; // Bu aralığın ilk elemanı
/*
* Asıl aralığın bir sonraki elemanını ara belleğin belirtilen elemanına
* okur
*/
void elemanOku(size_t hangiBayt)
{
araBellek[hangiBayt] = aralık.front;
aralık.popFront();
hazırBitler += toplamBit!E;
}
/*
* front()'un değerini hazırlar
*/
void ilkElemanıHazırla()
{
front_ = bitÇek(araBellek, konum, parçaGenişliği);
konum += parçaGenişliği;
hazırBitler -= parçaGenişliği;
}
this(R aralık)
{
this.aralık = aralık;
this.konum = 0;
this.hazırBitler = 0;
if (!this.aralık.empty) {
elemanOku(0);
if (!this.aralık.empty) {
elemanOku(1);
}
ilkElemanıHazırla();
} else {
// Boş olduğumuzu özel bir değerle belirt
this.hazırBitler = -1;
}
}
bool empty() const @property
{
return hazırBitler < 0;
}
E front() const @property
{
return front_;
}
void popFront()
{
if (hazırBitler < parçaGenişliği) {
// Hazırda yeterli bit yok
if (konum >= toplamBit!E) {
// Buraya geldiysek ikinci bayttan okumaktayız demektir. Yeni
// elemana yer açmak için ikinci baytı ilk bayta kaydırıyoruz.
araBellek[0] = araBellek[1];
konum -= toplamBit!E;
}
if (!aralık.empty) {
elemanOku(1);
} else {
// Asıl aralıkta eleman kalmamış. Son baytı boşaltalım.
araBellek[1] = E.init;
if (hazırBitler > 0) {
// En az bir bit daha sunmamız gerekiyor. Sondaki elemana
// erişilebilsin diye hazırdaki bitleri parça genişliğine
// eşitliyoruz.
hazırBitler = parçaGenişliği;
}
}
}
ilkElemanıHazırla();
}
}
/*
* BitParçaları aralığının kolaylık işlevi. Dizgileri doğru işleyebilmek için
* bundan iki tane yazmamız gerekti. Yoksa örneğin string'ler dchar aralıkları
* olarak ilerleniyorlardı ve o zaman her bir karakter 32 bit olarak
* genişlemis oluyordu.
*/
BitParçaları!(parçaGenişliği, R)
bitParçaları(size_t parçaGenişliği, R)(R aralık)
if (!(is (R : const(char)[]))) // "string değilse" anlamında. (wchar
// ile de ilgilenmek gerek ama şimdilik
// boşverdim.
{
return BitParçaları!(parçaGenişliği, R)(aralık);
}
/*
* Aynı kolaylık işlevinin string yüklemesi. string'ler ubyte aralıkları
* olarak işlenecekler.
*/
BitParçaları!(parçaGenişliği, ubyte[])
bitParçaları(size_t parçaGenişliği)(string aralık)
{
return bitParçaları!parçaGenişliği(cast(ubyte[])aralık);
}
unittest
{
// Sonda iki tane de 0 biti varsayılır
ubyte[] veri = [ 0b01110_101 ];
assert(bitParçaları!5(veri).array == [ 0b01110, 0b10100 ]);
}
unittest
{
// Bunu elle doldurdum. Her beşer bit artan değer taşıyor.
ubyte[] veri = [ 0b00000_000,
0b01_00010_0,
0b0011_0010,
0b0_00101_00,
0b110_00111,
0b01000_010,
0b01_01010_0,
0b1011_0110,
0b0_01101_00 ]; // Sonda üç tane 0 biti varsayılır.
assert(bitParçaları!5(veri).array
== [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 0 ]);
}
/*
* Bu aralık, asıl aralığın uzunluğu kısa bile olsa onu 'bölen'e tam bölünen
* bir uzunlukta gösterir. Örneğin 'bölen' 4 ise, aralıkta tek eleman bile
* olsa o tek eleman ve üç tane de doldurma elemanı olarak sunulur.
*/
struct UzunluğuTamBölünen(R)
{
R aralık;
size_t bölen;
ElementType!R doldurmaElemanı;
size_t toplamEleman;
this(R aralık, size_t bölen, ElementType!R doldurmaElemanı)
{
this.aralık = aralık;
this.bölen = bölen;
this.doldurmaElemanı = doldurmaElemanı;
}
bool empty() const @property
{
// Boş kabul edilebilmesi için toplam uzunluğun 'bölen'e tam bölünmesi
// gerekir.
return aralık.empty && !(toplamEleman % bölen);
}
ElementType!R front() const @property
{
// Asıl aralık boşsa kendimiz 'doldurmaElemanı' üretmeliyiz.
return aralık.empty ? doldurmaElemanı : aralık.front;
}
void popFront()
{
if (!aralık.empty) {
aralık.popFront();
}
++toplamEleman;
}
}
/*
* UzunluğuTamBölünen aralığının kolaylık işlevi
*/
UzunluğuTamBölünen!R
uzunluğuTamBölünen(R, E)(R aralık, size_t bölen, E doldurmaElemanı)
if (is (E : ElementType!R))
{
return UzunluğuTamBölünen!R(aralık, bölen, doldurmaElemanı);
}
unittest
{
assert(uzunluğuTamBölünen([ 1, 1, 1, 1, 1 ], 4, 42).array
== [ 1, 1, 1, 1, 1, 42, 42, 42 ]);
assert(uzunluğuTamBölünen([ 3 ], 8, 7).array
== [ 3, 7, 7, 7, 7, 7, 7, 7 ]);
}
/*
* Asıl aralığın elemanlarını belirtilen alfabeye erişen indeks değerleri
* olarak kullanır.
*/
struct Dönüştür(R)
{
R aralık;
string alfabe;
bool empty() const @property
{
return aralık.empty;
}
char front() const @property
{
return alfabe[aralık.front];
}
void popFront()
{
aralık.popFront();
}
}
/*
* Dönüştür'ün kolaylık işlevi.
*/
Dönüştür!R
dönüştür(R)(R aralık, string alfabe)
{
return Dönüştür!R(aralık, alfabe);
}
unittest
{
assert(dönüştür([ 0, 1, 3, 3, 7 ], "abcdefghi").array == "abddh");
}
enum Base32Alfabesi : string
{
Rfc4648 = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567=",
Rfc4648Hex = "0123456789ABCDEFGHIJKLMNOPQRSTUV=",
Crockford = "0123456789ABCDEFGHJKMNPQRSTVWXYZ=",
}
enum ubyte doldurmaKarakteriİndeksi = Base32Alfabesi.Rfc4648.length - 1;
/*
* Belirtilen aralığı Base32'ye dönüştürür. Dönüş türü tembel bir aralıktır.
*/
auto base32(T)(T veri, Base32Alfabesi alfabe = Base32Alfabesi.Rfc4648)
{
return (bitParçaları!5(veri)
.uzunluğuTamBölünen(8, doldurmaKarakteriİndeksi)
.dönüştür(alfabe));
}
unittest
{
ubyte[] a = [ 0b00000_000,
0b01_00010_0,
0b0011_0010,
0b0_00101_00,
0b110_00111,
0b01000_010,
0b01_01010_0,
0b1011_0110,
0b0_01101_11,
0b111_11111 ];
assert(base32(a).array == "ABCDEFGHIJKLMN77");
}
unittest
{
// Rfc4648 belgesindeki "test vectors" örnekleri
assert(base32("").array == "");
assert(base32("f").array == "MY======", base32("f").array);
assert(base32("fo").array == "MZXQ====");
assert(base32("foo").array == "MZXW6===");
assert(base32("foob").array == "MZXW6YQ=");
assert(base32("fooba").array == "MZXW6YTB");
assert(base32("foobar").array == "MZXW6YTBOI======");
assert(base32("", Base32Alfabesi.Rfc4648Hex).array == "");
assert(base32("f", Base32Alfabesi.Rfc4648Hex).array == "CO======");
assert(base32("fo", Base32Alfabesi.Rfc4648Hex).array == "CPNG====");
assert(base32("foo", Base32Alfabesi.Rfc4648Hex).array == "CPNMU===");
assert(base32("foob", Base32Alfabesi.Rfc4648Hex).array == "CPNMUOG=");
assert(base32("fooba", Base32Alfabesi.Rfc4648Hex).array == "CPNMUOJ1");
assert(base32("foobar", Base32Alfabesi.Rfc4648Hex).array
== "CPNMUOJ1E8======");
}
void main()
{}
--
[ Bu gönderi, http://ddili.org/forum'dan dönüştürülmüştür. ]
Permalink
Reply