Convert Base16 Hex String to Base58 String
Author 
Message 
JPB #1 / 25

Convert Base16 Hex String to Base58 String
I have a long (64 character, 256bit) Hex string that I am converting to a short (44 character) string in base 58. My Base 58 uses the
^_`abcdefghijklmnopqrstuvwxyz{}~ My current method works fine, but it is quite slow (converting 120,000 hex strings take about 15 minutes to convert on my dualcore 1.6gHz computer). I was wondering if anyone had any thoughts on some was to go about this efficiently. I can post my code if anyone is interested, but I thought I'd like to see some approach ideas before I did that. Here's an example in Base 16: E3B0C44298FC1C149AFBF4C8996FB92427AE41E4649B934CA495991B7852B855 And here's the Base 58 conversion: 47rw&lvh)!o9xs;0b5etfly$lx2f{,398qsgb#lqmzq Thanks in advance for any ideas.

Mon, 16 Jan 2012 05:32:16 GMT 


JPB #2 / 25

Convert Base16 Hex String to Base58 String
Another possibility is that I can get the 256bit string as a 32 element byte array. Anyone know of any fast methods to convert a byte array to an arbitrary base?

Mon, 16 Jan 2012 06:26:57 GMT 


Bob O`Bo #3 / 25

Convert Base16 Hex String to Base58 String
Quote:
> Another possibility is that I can get the 256bit string as a 32 > element byte array. Anyone know of any fast methods to convert a byte > array to an arbitrary base?
table lookup is going to be fastest at runtime.

Mon, 16 Jan 2012 07:09:33 GMT 


JPB #4 / 25

Convert Base16 Hex String to Base58 String
Quote: > table lookup is going to be fastest at runtime.
Hi Bob, thanks a lot for the reply. Sorry if I'm being a bit dense (I've been staring at code for a while), but I'm not sure how a lookup table can help me here, can you elaborate? I obviously can't do a full lookup table for every combination of 256 bit numbers, so what would I be putting in the lookup table? I should note (in case it wasn't clear) that I am trying to pack the entire 256 bit binary number into an arbitrary base, not just (let's say) convert each byte or X bytes into an arbitrary base & concatenate them. Thanks again for any additional information.

Mon, 16 Jan 2012 07:53:31 GMT 


Jim Mac #5 / 25

Convert Base16 Hex String to Base58 String
Quote:
>> table lookup is going to be fastest at runtime. > Hi Bob, thanks a lot for the reply. Sorry if I'm being a bit dense > (I've been staring at code for a while), but I'm not sure how a > lookup table can help me here, can you elaborate? > I obviously can't do a full lookup table for every combination of > 256 bit numbers, so what would I be putting in the lookup table? I > should note (in case it wasn't clear) that I am trying to pack the > entire 256 bit binary number into an arbitrary base, not just > (let's say) convert each byte or X bytes into an arbitrary base & > concatenate them. > Thanks again for any additional information.
You use a lookup table to translate the base 58 values into an appropriate symbol set. The values of the base 58 'digits' will range from 0 to 57, so the're not usable directly as printable characters. You'd create a 58entry array of characters  say, 09 followed by AZ followed by az or punctuation, etc. Then each digit indexes that array to produce the printable value. Think about how you'd do this for a common base, say 10: repeatedly divide the initial value by the base, using the remainders as the digit values and reducing the initial value each round by the result of (digit * base)  Jim Mack Twisted tees at http://www.cafepress.com/2050inc "We sew confusion"

Mon, 16 Jan 2012 08:51:50 GMT 


JPB #6 / 25

Convert Base16 Hex String to Base58 String
Thanks for the reply Jim.
Quote: > You use a lookup table to translate the base 58 values into an > appropriate symbol set. The values of the base 58 'digits' will range > from 0 to 57, so the're not usable directly as printable characters. > You'd create a 58entry array of characters  say, 09 followed by > AZ followed by az or punctuation, etc. Then each digit indexes that > array to produce the printable value.
Okay, this is no problem, thank you. Quote: > Think about how you'd do this for a common base, say 10: repeatedly > divide the initial value by the base, using the remainders as the > digit values and reducing the initial value each round by the result > of (digit * base)
I think I understand the concept, but performing arithmetic on 256 bit numbers won't fit into any VB6 data type AFAIK. Should I be breaking up the 256bit number into 8 chunks of 32bit numbers and processing each of those separately and then concatenating the results? Or is there a better way?

Mon, 16 Jan 2012 09:40:22 GMT 


JPB #7 / 25

Convert Base16 Hex String to Base58 String
By packing the 256bit number into 7 Currency variables in a UDT (I used Currency in order to hold unsigned long values), and using your recommendations, I improved the speed of my original code tremendously...120000 runs now takes just over 1 minute (this includes the hashing overhead) instead of ~15 minutes, and this is pre optimization. The only problem right now is that the new algorithm is not as efficient packing wise (up to 48 chars instead of 44 characters for the original algorithm). I assume this is because the unsigned long packing into currency variables isn't using the maximum available bits. The extra four characters is worth the speed increase though. Once I have optimized and cleaned up my code I will post it here. Thanks again Bob and Jim!

Mon, 16 Jan 2012 11:10:42 GMT 


Larry Serflate #8 / 25

Convert Base16 Hex String to Base58 String
I obviously can't do a full lookup table for every combination of 256 bit numbers, so what would I be putting in the lookup table?  The table of powers for your base. If you have a 16 byte array of bit values, keep a table of 16 byte arrays containing the bit representation of the base rasied exponentialy. For example, for the base of 64 (just for ease of use) using Hex notation (for a 16 byte array) would be filled like 0 = 00000000000000000000000000000001 1 = 00000000000000000000000000000040 2 = 00000000000000000000000000001000 3 = 00000000000000000000000000040000 4 = 00000000000000000000000000100000 5 = 00000000000000000000000004000000 ... etc... (where each 2 digits is one byte of the array) For a base of 58 it would be more like: 0 = 00000000000000000000000000000001 1 = 0000000000000000000000000000003A 2 = 00000000000000000000000000000D24 3 = 0000000000000000000000000002FA28 Now you can see, when you have an array that is (whatever) 1D038A9C002DEB05A8004002ADB0703A You find the highest element that is less than your value and start subtracting out the element value from the initial value. As Jim said, think how you'd do it if it was all base 10. With an intial value of 354824 you'd find your 5th element has 100000 which is just less than the initial value, and you subtract it out 3 times to produce a new value of 54824. etc. There are optimizations you can add to avoid so many (user defined) subraction operations, but getting the concept down and working would be the first step.... LFS

Mon, 16 Jan 2012 12:17:08 GMT 


JPB #9 / 25

Convert Base16 Hex String to Base58 String
Here's the code I have so far, which (upon just reading Larry's post) won't be my last attempt ;) Private Type HashChunks Chunk(0 To 7) As Currency End Type Private Const csValidChars As String =
Public Function ByteArrayToFileBaseString(p_Bytes() As Byte) As String Static s_Initialized As Boolean Static sa_BaseChars() As String Static sa_Converted() As Byte Static s_Base As Long Dim i As Long Dim l_Remainder As Long Dim lt_Chunks As HashChunks Dim l_CurrentByte As Long Dim l_Quotient As Currency If Not s_Initialized Then s_Initialized = True sa_Converted = String$(96, 0) sa_BaseChars = Split("0 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k
{ } ~", " ") s_Base = UBound(sa_BaseChars) + 1 End If ' Pack the byte array into a UDT of currency variables ' To be as efficient as I know how to work with unsigned longs For i = 0 To 7 CopyMemory lt_Chunks.Chunk(i), p_Bytes(i * 4), 4 lt_Chunks.Chunk(i) = lt_Chunks.Chunk(i) * 10000 Next i ' Convert the packed values into arbitrary base characters l_CurrentByte = UBound(sa_Converted)  1 For i = 0 To 7 Do While lt_Chunks.Chunk(i) > 0 l_Quotient = Fix(lt_Chunks.Chunk(i) / s_Base) ' The remainder will be an arbitrary base character l_Remainder = lt_Chunks.Chunk(i)  (l_Quotient * s_Base) sa_Converted(l_CurrentByte) = AscB(sa_BaseChars(l_Remainder)) ' move our current byte pointer back by 2 digits to account for ' unicode (2 byte) encoding l_CurrentByte = l_CurrentByte  2 lt_Chunks.Chunk(i) = l_Quotient Loop Next i ' Return the converted string with leading unfilled bytes removed ByteArrayToFileBaseString = Mid$(sa_Converted, (l_CurrentByte \ 2) + 2) End Function While much faster (by an order of a magnitude or more) than my previous algorithm, it suffers from the following problems: 1) Doesn't produce identical results to my previous algorithm (not a huge issue since I am still in the early stages of design, so as long as the ultimate result is consistent) 2) Produces slightly longer converted strings because the byte packing isn't 100% efficient. The good news is that my early tests produce consistent results, so it is certainly usable if I can't figure out how to get 100% efficient bit packing and conversion (without a speed penalty). I still have to study Larry's reply further and see what I can produce. If I get it solved, I will post back the improved code here as well in case anyone else can find a use for it. (NOTE: I realize that using Statics and testing for initializing is a spot for improvement, I just wanted to keep the code contained for the sample purposes here. You can optimize that out by preinitializing those variables outside of the function or in a Class_Initialize event).

Mon, 16 Jan 2012 12:34:09 GMT 


JPB #10 / 25

Convert Base16 Hex String to Base58 String
Hi Larry, Thanks a lot for that reply, it looks very helpful. I'm off to bed shortly, but I will try to digest the information you've provided in the morning and see if I can improve my code.

Mon, 16 Jan 2012 12:35:34 GMT 


JPB #11 / 25

Convert Base16 Hex String to Base58 String
Hi Larry, Since I have a 32byte array value (in base 256), I've precomputed a 33 element array of Base 58 exponent values (including ^0) to achieve the following: 00000000000000000000000000000000000000000000001 0000000000000000000000000000000000000000000003A 00000000000000000000000000000000000000000000D24 0000000000000000000000000000000000000000002FA28 00000000000000000000000000000000000000000ACAD10 000000000000000000000000000000000000000271F35A0 000000000000000000000000000000000000008DD122640 000000000000000000000000000000000000202161CAA80 000000000000000000000000000000000007479027EA100 0000000000000000000000000000000001A636A90B07A00 000000000000000000000000000000005FA8624C7FBA400 00000000000000000000000000000015AC264554F032800 000000000000000000000000000004E900ABB53E6B71000 00000000000000000000000000011CCA26E71024579A000 000000000000000000000000004085CCD059A83BD8E4000 0000000000000000000000000E9E506734501D8F23A8000 0000000000000000000000034FDE3761DA26B26E1410000 0000000000000000000000C018588C2B6CC46CF08BA0000 000000000000000000002B85840FC1D6A480AE7FA240000 00000000000000000009DC3FEB91EAA1452788EAC280000 0000000000000000023BE67B5F0F2889AAF505301100000 0000000000000000819237F3896F2F30BB832CE3DA00000 000000000000001D5B20AD2D2330B10A7BB82B9F6400000 00000000000006A6A5673C39F9081C6007B9E21CA800000 00000000000181C17963A5226BD66DC1C01D3A7E1000000 00000000005765D5809369CC6E94DDE5869F408FA000000 0000000013CD125F2165F8510DBA46008014A08A4000000 000000047C76298D911A425D1C33DC1D04AC5F528000000 0000010432C56A12DFF3091863BFDE930F0D98B10000000 00003AF380BA0846BD100F8699786D516914981A0000000 000D5B2B2A25E006D5A3847EC548C471CEAA75E40000000 0306A7C78C94C18C670C04B8B27C81C8D29EB5A80000000 AF820335D9B3D9CF58B911D87035677FB7F528100000000 So my largest precomputed value is 47 hex values which translates into 24 bytes in binary. Have I calculated enough values, or do I need to get up to 32bytes of binary in Base 58? Also, do you have any recommendations on how best to perform the required subtraction on 2 bytes arrays? Thanks again for any further help.

Tue, 17 Jan 2012 01:17:55 GMT 


JPB #12 / 25

Convert Base16 Hex String to Base58 String
So far, I've gotten as far as precomputing the power of 58 values into a Byte array and I have been able to compare a base 256 byte array to my precomputed values in order to find the first item lower than the passed value. It *seems* to be working okay using the following code: ' ******************* START OF CODE Option Explicit Private Declare Sub CopyMemory Lib "kernel32.dll" Alias "RtlMoveMemory" (ByRef Destination As Any, ByRef Source As Any, ByVal Length As Long) Private ma_Lookup(31, 32) As Byte ' Lookup table of powers of 58 for 32byte numeric comparisons Public Sub InitLookupTable() Dim i As Long Dim l_ByteHex As String Dim j As Long Dim l_Hex As String ' Populate a lookup table of powers of 58 in bytes For i = 0 To 32 l_Hex = GetLookupTableEntryHex(i) For j = 1 To Len(l_Hex) Step 2 l_ByteHex = Mid$(l_Hex, j, 2) If l_ByteHex <> "00" Then ma_Lookup(j \ 2, i) = CByte("&H" & l_ByteHex) End If Next j Next i End Sub Public Function GetLookupTableEntryBytes(ByVal p_PowerOf58 As Long) As Byte() ' Convert an entry from our 2dimensional lookup table into a 1 dimensional byte array and return it Dim la_Bytes(31) As Byte ReDim GetLookupTableEntry(31) CopyMemory la_Bytes(0), ma_Lookup(0, p_PowerOf58), 32 GetLookupTableEntryBytes = la_Bytes End Function Public Function GetLookupTableEntryHex(p_PowerOf58 As Long) As String Dim l_Hex As String Select Case p_PowerOf58 Case 0 l_Hex = "000000000000000000000000000000000000000000000001" Case 1 l_Hex = "00000000000000000000000000000000000000000000003A" Case 2 l_Hex = "000000000000000000000000000000000000000000000D24" Case 3 l_Hex = "00000000000000000000000000000000000000000002FA28" Case 4 l_Hex = "000000000000000000000000000000000000000000ACAD10" Case 5 l_Hex = "0000000000000000000000000000000000000000271F35A0" Case 6 l_Hex = "0000000000000000000000000000000000000008DD122640" Case 7 l_Hex = "0000000000000000000000000000000000000202161CAA80" Case 8 l_Hex = "0000000000000000000000000000000000007479027EA100" Case 9 l_Hex = "00000000000000000000000000000000001A636A90B07A00" Case 10 l_Hex = "0000000000000000000000000000000005FA8624C7FBA400" Case 11 l_Hex = "000000000000000000000000000000015AC264554F032800" Case 12 l_Hex = "0000000000000000000000000000004E900ABB53E6B71000" Case 13 l_Hex = "000000000000000000000000000011CCA26E71024579A000" Case 14 l_Hex = "0000000000000000000000000004085CCD059A83BD8E4000" Case 15 l_Hex = "00000000000000000000000000E9E506734501D8F23A8000" Case 16 l_Hex = "00000000000000000000000034FDE3761DA26B26E1410000" Case 17 l_Hex = "00000000000000000000000C018588C2B6CC46CF08BA0000" Case 18 l_Hex = "0000000000000000000002B85840FC1D6A480AE7FA240000" Case 19 l_Hex = "000000000000000000009DC3FEB91EAA1452788EAC280000" Case 20 l_Hex = "00000000000000000023BE67B5F0F2889AAF505301100000" Case 21 l_Hex = "00000000000000000819237F3896F2F30BB832CE3DA00000" Case 22 l_Hex = "0000000000000001D5B20AD2D2330B10A7BB82B9F6400000" Case 23 l_Hex = "000000000000006A6A5673C39F9081C6007B9E21CA800000" Case 24 l_Hex = "000000000000181C17963A5226BD66DC1C01D3A7E1000000" Case 25 l_Hex = "000000000005765D5809369CC6E94DDE5869F408FA000000" Case 26 l_Hex = "00000000013CD125F2165F8510DBA46008014A08A4000000" Case 27 l_Hex = "0000000047C76298D911A425D1C33DC1D04AC5F528000000" Case 28 l_Hex = "00000010432C56A12DFF3091863BFDE930F0D98B10000000" Case 29 l_Hex = "000003AF380BA0846BD100F8699786D516914981A0000000" Case 30 l_Hex = "0000D5B2B2A25E006D5A3847EC548C471CEAA75E40000000" Case 31 l_Hex = "00306A7C78C94C18C670C04B8B27C81C8D29EB5A80000000" Case 32 l_Hex = "0AF820335D9B3D9CF58B911D87035677FB7F528100000000" End Select GetLookupTableEntryHex = l_Hex End Function Public Function ConvertBase256ToBase58(p_Base256() As Byte) As String Static s_Initialized As Boolean Dim i As Long If Not s_Initialized Then s_Initialized = True InitLookupTable End If ' Find the first entry in our lookup table that is lower than the passed For i = 32 To 0 Step 1 ' Counting backwards is an optimization since most of the input byte arrays are going to be index>=30 in our lookup table If StrComp(p_Hex, GetLookupTableEntryBytes(i), vbBinaryCompare) Quote: > 0 Then
Exit For End If Next i ' TODO: Start conversion against found lookup table entry End Function ' ************************* END OF CODE My questions are: 1) What would be the best way to subtract large byte arrays from each other? 2) When performing the subtractions, how I am supposed to proceed? : 1) Subtract the byte array from the lookup table from the original byte array until we have a byte array that is less than the lookup table byte array. 2) Locate the index in our lookup table that is lower than the result of our subtraction and repeat step 1. 3) Repeat these steps until we have a value <= our conversion Base (Base 58) and store that value in our result byte array. 4) What should my new starting value be to find the next base 58 "byte"? Or are those steps totally offbase? Thanks again for any help.

Tue, 17 Jan 2012 04:58:07 GMT 


Larry Serflate #13 / 25

Convert Base16 Hex String to Base58 String
Quote: > ' TODO: Start conversion against found lookup table entry > End Function
I deliberately let you think about this a while. It is all pretty straight forward, elementary stuff, once you break down to component tasks. Quote: > My questions are: > 1) What would be the best way to subtract large byte arrays from each > other?
There is only one way, loop through the array subtracting one array element from the other, and storing the result in a third array. Quote: > 2) When performing the subtractions, how I am supposed to proceed? : > 1) Subtract the byte array from the lookup table from the original > byte array until we have a byte array that is less than the lookup > table byte array. > 2) Locate the index in our lookup table that is lower than the result > of our subtraction and repeat step 1. > 3) Repeat these steps until we have a value <= our conversion Base > (Base 58) and store that value in our result byte array. > 4) What should my new starting value be to find the next base 58 > "byte"?
Perhaps this will help: Keep an eye on what your result needs to be; an array that represents the 256 bit value. Element 0 is going to be how many ones you have, element 1 is going to be how many <base> units you have, element 2 is going to be how many <base * base> units you have and so on. Element 3 is going to be base ^ 3 units, element 4 is base ^ 4 units, etc... As it happens, the LSB and MSB will be the reverse of how you'd want to display it, but as long as you're aware of the correct order, the computer doesn't care how your array is ordered. You can operate on it in the way that makes most sense to you. So there you have it, once you find what exponential array (from your array of exponential arrays) is just less than the 256 bit array you have, you know the index of that exponential array is the index of your result that you will be working with. You just need to know how many times you can subtract out that specific exponential array from your 256 bit array without causing an underflow. The number of subtractions you can perform is the value that will be stored at the index you found. From there you move to the next lower index in your exponential array (and next lower index in your result) and record the number of subtractions you can perform there. Continuing that process until you get to the 0th element. But consider this, with a base of 58, you might (at some point) perform 57 subtractions to find the value you need to store. If, however, you right shift your subtractor by 4 bits, and used that in the subtraction, that would be like making 16 individual subtractions, from just one subtract operation. That is a little optimization you might test for and consider.... LFS

Wed, 18 Jan 2012 07:46:50 GMT 


JPB #14 / 25

Convert Base16 Hex String to Base58 String
Quote: > I deliberately let you think about this a while. ?It is all pretty straight forward, > elementary stuff, once you break down to component tasks.
No problem, thanks for helping at all! Even though it is straight forward, it does seem to break my brain a bit, but I'm getting the hang of it. Quote: > There is only one way, loop through the array subtracting one array element > from the other, and storing the result in a third array.
Okay, this is working fine (taking into account overflows and borrowing as well). Thanks. Quote: > Keep an eye on what your result needs to be; an array that represents > the 256 bit value. ?Element 0 is going to be how many ones you have, > element 1 is going to be how many <base> units you have, element > 2 is going to be how many <base * base> units you have and so on. > Element 3 is going to be base ^ 3 units, element 4 is base ^ 4 units, etc...
Makes sense, which is to say I am with you here. Quote: > As it happens, the LSB and MSB will be the reverse of how you'd > want to display it, but as long as you're aware of the correct order, > the computer doesn't care how your array is ordered. ?You can operate > on it in the way that makes most sense to you.
Also not a problem, I can loop backwards or forwards as required. Quote: >?You just need to know how many times > you can subtract out that specific exponential array from your 256 bit > array without causing an underflow. ?The number of subtractions you > can perform is the value that will be stored at the index you found.
Ah! That was a piece of the puzzle that I was missing. I did not realize that the number of subtractions would be my new byte. This is a big help (obviously). Quote: > But consider this, with a base of 58, you might (at some point) perform > 57 subtractions to find the value you need to store. ?If, however, you > right shift your subtractor by 4 bits, and used that in the subtraction, > that would be like making 16 individual subtractions, from just one > subtract operation. ?That is a little optimization you might test for and > consider....
I'm not sure I understand the rightshift, or what I would test for to determine if I need it, but let me stew on that a while. So far my results are close to the results from my old algorithm...but there is a sudden divergence after a few characters which is odd. Maybe I miscalculated or entered one of my powers of 58...I'll keep digging and post back a working function when I get there. Thanks again for all of your help, I really appreciate it.

Wed, 18 Jan 2012 11:10:02 GMT 


Larry Serflate #15 / 25

Convert Base16 Hex String to Base58 String
Quote: > I'm not sure I understand the rightshift, or what I would test for to > determine if I need it, but let me stew on that a while.
My bad, that should have been LEFT shift. Here's an example., I'm not going to use the whole 32 bytes, I'll just use the first few, where the action is, just pretend the rest are trailing off to the right.... (Im also just picking arbitrary values, I don't have the full power table....) Your value is: 00 96 C3 F1 (...) Nearest power is: 00 03 AB 72 (...) With those, you'd end up making about 40 subtractions to find the value you want to store. If you LEFT shift the subtractor by 4 bits you get: Your value is: 00 96 C3 F1 (...) New subractor: 00 3A B7 20 (...) You could then subract that value out twice (equivalent to 32 subtractions of the power value) and then finish subtracting out the power value another 8 (or so) times. What that does is reduces the number of subtractions you need to perform. In this case the reduction was from 40, to 10 (2 + 8) subtraction operations. The test can be rather simple, here is it is listed as tasks: Find digit index of power array (just less than 256 Value) Find index of the first nonzero byte in 256 array, call that FirstByte Get the value from 256 array at FirstBye index. Call that FBvalue. (96  see above) Get value from power array at FirstByte index. Call that FBpower. (03  see above) If (FBpower * 16) < FBValue Then you can apply Left shift Else subract out the power value until just before underflow. I mentioned a left shift of 4 bits because that would suit your situation, (and its easy to do) but you could shift by any number of bits, as long as you adjust your result digit accordingly. You know it will be a trade off, how much effort you want to spend, for how much gain in speed. I'd suggest just the 1 option (shift 4 bits up, or not) would be the sweet spot, in that you get a speed increase of about 400% (~1/4 reduction in time) if you test for and apply the shift trick. Good luck! LFS

Thu, 19 Jan 2012 01:11:49 GMT 


Page 1 of 2

[ 25 post ] 

Go to page:
[1]
[2] 
