|
|
Post by VDC 8x2 on Aug 26, 2014 8:03:25 GMT
far 8 copy complete now.
now to clean up and work on user friendliness.
compressed the 37 block test file into a 15 block file
Lots of pictures to test too.
Module Module1
Sub Main()
Dim outputString As String = ""
Dim starting() As Byte = {0}
Dim stringCount As UInteger
Dim historyPointer As Integer = 0
Dim processPointer As Integer = 1
Dim futurePointer As UInteger = 256
Dim endOfProcess As Integer
Dim farSize As Integer
Dim raw As String = ""
Dim compressTarget As String = ""
Dim anyCompression As Integer
Dim bytes = My.Computer.FileSystem.ReadAllBytes("D:/Emulation/drive10/testdata.prg")
'convert array into our workstring
For index = 0 To bytes.GetUpperBound(0)
compressTarget = compressTarget & Chr(bytes(index))
Next
endOfProcess = Len(compressTarget)
'start of the encoding loop
Do
stringCount = 1
anyCompression = 0
'big copy mirror
If historyPointer > 257 Then
If futurePointer = 256 Then
stringCount = futurePointer
If Mid(compressTarget, processPointer - 257, stringCount) = Mid(compressTarget, processPointer + 256, stringCount) Then
anyCompression = 2
End If
End If
End If
'64 mirror copy
If anyCompression = 0 Then
If historyPointer > 65 Then
If futurePointer > 63 Then
stringCount = 64
Else
stringCount = futurePointer
End If
Do
If Mid(compressTarget, processPointer - stringCount - 1, stringCount) = Mid(compressTarget, processPointer + stringCount, stringCount) Then
anyCompression = 2
Exit Do
Else
stringCount = stringCount - 1
If stringCount = 1 Then
Exit Do
End If
End If
Loop
End If
End If
'64byte far copy
If anyCompression = 0 Then
'has to be 64 bytes or more in the future and history buffer for this to work
If futurePointer > 63 And historyPointer > 65 Then
stringCount = historyPointer
farSize = 64
Do
If Mid(compressTarget, processPointer - stringCount, farSize) = Mid(compressTarget, processPointer, farSize) Then
anyCompression = 3
Exit Do
Else
stringCount = stringCount - 1
If stringCount < 65 Then 'nothing found so set stringCount for the next check
stringCount = 1
Exit Do
End If
End If
Loop
End If
End If
'rle copy for 256 or 64 bytes
If anyCompression = 0 Then
Do
If Mid(compressTarget, processPointer, 1) = Mid(compressTarget, processPointer + stringCount, 1) Then
stringCount = stringCount + 1
anyCompression = 1
If stringCount = futurePointer Then
Exit Do
End If
Else
Exit Do
End If
Loop
End If
If anyCompression = 0 Then 'far copy 8 byte
If futurePointer > 7 And historyPointer > 9 Then
farSize = 8
Do
stringCount = historyPointer
Do
If Mid(compressTarget, processPointer - stringCount, farSize) = Mid(compressTarget, processPointer, farSize) Then
anyCompression = 3
Exit Do
Else
stringCount = stringCount - 1
If stringCount < 9 Then 'nothing found so set stringCount for the next check
Exit Do
End If
End If
Loop
If anyCompression = 3 Then
Exit Do
End If
farSize = farSize - 1
If farSize = 1 Then
stringCount = 1
Exit Do
End If
Loop
End If
End If
'if any compression happened then flush raw buffer
If anyCompression > 0 Then
If Len(raw) <> 0 Then
outputString = outputString & Chr(Len(raw) * 4) & raw
raw = ""
End If
End If
'process 64 byte far copy
If anyCompression = 3 Then
If farSize = 64 Then 'hhhlllxx with xx =11 lllllsss with sss = farsize-1
outputString = outputString & Chr((stringCount And 2016) / 8 + 3) & Chr((stringCount And 31) * 8)
stringCount = farSize
Else
outputString = outputString & Chr((stringCount And 2016) / 8 + 3) & Chr((stringCount And 31) * 8 + (farSize - 1))
stringCount = farSize
End If
End If
'process mirror packet
If anyCompression = 2 Then
If stringCount = 256 Then
outputString = outputString & Chr(1)
Else
outputString = outputString & Chr((stringCount - 1) * 4 + 1)
End If
End If
'process rle packet
If anyCompression = 1 Then
If stringCount = 256 Then
outputString = outputString & Chr(2) & Mid(compressTarget, processPointer, 1)
Else
If stringCount > 64 Then
stringCount = 64
End If
outputString = outputString & Chr((stringCount - 1) * 4 + 2) & Mid(compressTarget, processPointer, 1)
End If
End If
If anyCompression = 0 Then
raw = raw & Mid(compressTarget, processPointer, 1)
'if raw has reached 63 bytes then flush the buffer to output and clear
If Len(raw) = 63 Then
outputString = outputString & Chr(63 * 4) & raw
raw = ""
End If
End If
historyPointer = historyPointer + stringCount
If historyPointer > 2048 Then
historyPointer = 2048
End If
processPointer = processPointer + stringCount
If processPointer + futurePointer > endOfProcess Then
futurePointer = futurePointer - (processPointer + futurePointer - endOfProcess)
End If
If futurePointer = 0 Then
'if any raw left in buffer then flush out before ending
If Len(raw) <> 0 Then
outputString = outputString & Chr(Len(raw) * 4) & raw
raw = ""
End If
outputString = outputString & Chr(0)
Exit Do
End If
Loop
Dim outputFile(Len(outputString)) As Byte
For index = 1 To Len(outputString)
outputFile(index) = Asc(Mid(outputString, index, 1))
Next
My.Computer.FileSystem.WriteAllBytes("D:/Emulation/drive10/outputData.prg", starting, False)
My.Computer.FileSystem.WriteAllBytes("D:/Emulation/drive10/outputData.prg", outputFile, True)
End Sub
End Module
|
|
|
|
Post by hydrophilic on Aug 26, 2014 8:59:52 GMT
Thanks for the comments, those help a lot. I see you got far copy in there too. 37 blocks down to 15 is over 50%... (59.5% if my math is right). That's really good for a simple byte code... in fact it seems too good. Well obviously it depends on the type of image. A computer-generated image (from Doodle or GeoPaint etc.) would probably give results like that. Since you are wanting to use this with your game (I imagine) that is probably a good metric. I would be really surprised to see a real photo (like in this thread) get a compression that good (due to the irregularity caused by dithering). Your code is pretty simple and straight-forward right now. You might want to stop there is multiple images that you consider important get a ratio around 50%. Obviously you can tweek it to improve the performance, and it some cases it might be considerable performance, but in most cases I think you'll find only marginal improvement despite a lot of work. Well that's what happened to me... Like you were talking about "solving" the problem of using a copy code instead of 2 RLE codes in row when the copy version would provide better compression. So to fix that, and all similar problems, you would generally need to try all possibilities and note the "cost" of each. Right now (unless I misunderstand) it does not try any alternatives once it sees a "higher priority" match... Umm, like if it finds any copy amount (anyCompression=2) then it never tries RLE. When I implemented the "cost" factor in my code, it made it much slower (because it keeps testing other methods even though it already found one encoding) and also a bit messier (tracking and comparing the various costs). The end result only improved general images a few percent (but for some images it might be "significant" like 4% or 8%). Another thing which can make an even bigger improvement in some images (not sure about general images) is to not use the "greedy" strategy that you now use. You can read about this in most any text on compression. The optimal method is to use a "delayed" strategy. This makes the code more complex and slower, because with it you essentially compress the file twice (in small chunks at time) and select the best between two alternatives... it is kind of like the "cost" factor discussed above, but on steroids. You might be able to do it inline, but for sanity, you would probably want to implement a subroutine. I did very limited work on this myself, and never fully implemented it because the returns did not seem to be worth the effort... and also I wanted my video encoder to be fast, which the "delayed" strategy is definately not. It really comes down to how much time you want to invest and what compression is good enough for your purposes. |
|
|
|
Post by VDC 8x2 on Aug 26, 2014 18:26:27 GMT
The main reason I weighted copy higher then rle is, I wanted to reduce the amount of data I have to push through the vdc data register.
Right now the code is doing rle before any copy8 far.
|
|
|
|
Post by hydrophilic on Aug 27, 2014 5:12:40 GMT
Good point about the VDC bottleneck.
|
|
|
|
Post by VDC 8x2 on Aug 27, 2014 22:25:13 GMT
Having mirror, far copy and rle compete now.
aside from making it user friendlier, the code is finalized imo.
Module Module1
Sub Main()
Dim outputString As String = ""
Dim starting() As Byte = {0}
Dim historyPointer As Integer = 0
Dim processPointer As Integer = 1
Dim futurePointer As UInteger = 256
Dim endOfProcess As Integer
Dim updatePointer As UInteger
Dim farSize As Integer
Dim raw As String = ""
Dim compressTarget As String = ""
Dim anyCompression(3) As UInteger
Dim stringCount(3) As UInteger
Dim bytes = My.Computer.FileSystem.ReadAllBytes("D:/Emulation/drive10/testdata.prg")
'convert array into our workstring
For index = 0 To bytes.GetUpperBound(0)
compressTarget = compressTarget & Chr(bytes(index))
Next
endOfProcess = Len(compressTarget)
'start of the encoding loop
Do
For index = 0 To 3 'making 3 to compete against each other
stringCount(index) = 1
anyCompression(index) = 0
Next
'256 mirror copy
If anyCompression(2) = 0 Then
If historyPointer > 257 Then
If futurePointer = 256 Then
stringCount(2) = futurePointer
If Mid(compressTarget, processPointer - 257, stringCount(2)) = Mid(compressTarget, processPointer + 256, stringCount(2)) Then
anyCompression(2) = stringCount(2)
End If
End If
End If
End If
'64 mirror copy
If anyCompression(2) = 0 Then
If historyPointer > 65 Then
If futurePointer > 63 Then
stringCount(2) = 64
Else
stringCount(2) = futurePointer
End If
Do
If Mid(compressTarget, processPointer - stringCount(2) - 1, stringCount(2)) = Mid(compressTarget, processPointer + stringCount(2), stringCount(2)) Then
anyCompression(2) = stringCount(2)
Exit Do
Else
stringCount(2) = stringCount(2) - 1
If stringCount(2) = 1 Then
Exit Do
End If
End If
Loop
End If
End If
'64byte far copy
If anyCompression(3) = 0 Then
'has to be 64 bytes or more in the future and history buffer for this to work
If futurePointer > 63 And historyPointer > 65 Then
stringCount(3) = historyPointer
farSize = 64
Do
If Mid(compressTarget, processPointer - stringCount(3), farSize) = Mid(compressTarget, processPointer, farSize) Then
anyCompression(3) = farSize
Exit Do
Else
stringCount(3) = stringCount(3) - 1
If stringCount(3) < 65 Then 'nothing found so set stringCount for the next check
Exit Do
End If
End If
Loop
End If
End If
If anyCompression(3) = 0 Then 'far copy 8 byte
If futurePointer > 7 And historyPointer > 9 Then
farSize = 8
Do
stringCount(3) = historyPointer
Do
If Mid(compressTarget, processPointer - stringCount(3), farSize) = Mid(compressTarget, processPointer, farSize) Then
anyCompression(3) = farSize
Exit Do
Else
stringCount(3) = stringCount(3) - 1
If stringCount(3) < farSize + 1 Then 'nothing found so set stringCount for the next check
Exit Do
End If
End If
Loop
If anyCompression(3) > 0 Then
Exit Do
End If
farSize = farSize - 1
If farSize = 1 Then
Exit Do
End If
Loop
End If
End If
'rle for 256 or 64 bytes
If anyCompression(1) = 0 Then
Do
If Mid(compressTarget, processPointer, 1) = Mid(compressTarget, processPointer + stringCount(1), 1) Then
stringCount(1) = stringCount(1) + 1
anyCompression(1) = 1
If stringCount(1) = futurePointer Then
Exit Do
End If
Else
Exit Do
End If
Loop
If anyCompression(1) > 0 Then
If stringCount(1) > 64 And stringCount(1) < 256 Then 'out of bounds so truncate it
anyCompression(1) = 64
stringCount(1) = 64
Else
anyCompression(1) = stringCount(1)
End If
End If
End If
'if any compression happened then flush raw buffer
If anyCompression(1) > 0 Or anyCompression(2) > 0 Or anyCompression(3) > 0 Then
If Len(raw) <> 0 Then
outputString = outputString & Chr(Len(raw) * 4) & raw
raw = ""
End If
'process 64 byte far copy
If anyCompression(3) >= anyCompression(1) And anyCompression(3) >= anyCompression(2) Then
'Console.WriteLine("far copy " & anyCompression(3))
If anyCompression(3) = 64 Then 'hhhlllxx with xx =11 lllllsss with sss = farsize-1
outputString = outputString & Chr((stringCount(3) And 2016) / 8 + 3) & Chr((stringCount(3) And 31) * 8)
updatePointer = anyCompression(3)
Else
outputString = outputString & Chr((stringCount(3) And 2016) / 8 + 3) & Chr((stringCount(3) And 31) * 8 + (anyCompression(3) - 1))
updatePointer = anyCompression(3)
End If
ElseIf anyCompression(2) >= anyCompression(1) Then
'process mirror packet
'Console.WriteLine("mirror " & anyCompression(2))
If anyCompression(2) = 256 Then
outputString = outputString & Chr(1)
updatePointer = 256
Else
outputString = outputString & Chr((anyCompression(2) - 1) * 4 + 1)
updatePointer = anyCompression(2)
End If
Else
'process rle packet
'Console.WriteLine("rle " & anyCompression(1))
If anyCompression(1) = 256 Then
outputString = outputString & Chr(2) & Mid(compressTarget, processPointer, 1)
updatePointer = 256
Else
outputString = outputString & Chr(anyCompression(1) - 1 * 4 + 2) & Mid(compressTarget, processPointer, 1)
updatePointer = anyCompression(1)
End If
End If
Else
raw = raw & Mid(compressTarget, processPointer, 1)
updatePointer = 1
'Console.WriteLine("raw")
'if raw has reached 63 bytes then flush the buffer to output and clear
If Len(raw) = 63 Then
outputString = outputString & Chr(63 * 4) & raw
raw = ""
End If
End If
historyPointer = historyPointer + updatePointer
If historyPointer > 2048 Then
historyPointer = 2048
End If
processPointer = processPointer + updatePointer
If processPointer + futurePointer > endOfProcess Then
futurePointer = futurePointer - (processPointer + futurePointer - endOfProcess)
End If
If futurePointer = 0 Then
'if any raw left in buffer then flush out before ending
If Len(raw) <> 0 Then
outputString = outputString & Chr(Len(raw) * 4) & raw
raw = ""
End If
outputString = outputString & Chr(0)
Exit Do
End If
Loop
Dim outputFile(Len(outputString)) As Byte
For index = 1 To Len(outputString)
outputFile(index) = Asc(Mid(outputString, index, 1))
Next
My.Computer.FileSystem.WriteAllBytes("D:/Emulation/drive10/outputData.prg", starting, False)
My.Computer.FileSystem.WriteAllBytes("D:/Emulation/drive10/outputData.prg", outputFile, True)
'Console.ReadLine()
End Sub
End Module
|
|
|
|
Post by hydrophilic on Aug 28, 2014 6:02:54 GMT
Cool. Glad you got all the parts working, and now (so I see) you have "anyCompression" in an array so you compare options to pick the best for the current position. This is what I would call level 1 optimization, and is probably sufficient for most purposes. What I call level 0 optimization would be re-allocating the bit-codes. I discussed this a long time ago, but to keep people from having to find that post, I'll repeat myself. So you need a good collection of images (nice variety). Then you can try compressing them using different bit allocations. The best example is probably Far Copy: you might get better compression (in general, after testing many images) by using 10-bit distance and 4-bit count (as opposed to the current version with 11-bit distance and 3-bit count). Well there are numerous ways to assign codes and I don't feel like trying to explain them all... the important thing about level 0 optimization is it is a royal pain! You have to update both the VBASIC Encoder, and the C128 Decoder to test new methods. What I call level 2 optimization is the opposite direction... you don't need to update the C128 Decoder, but you need to make the VBASIC code more generic. Essentially, you put most of everything you've done into a subroutine (except reading the source file, pointer initialization, and writing the file). Then you proceed until you a get "real" (non-raw) code... when that happens, you "memorize" how many bytes the code needs, and where the next address would be. But then you continue as if that code was not possible (next best option). In the continuation scenario, when you finally reach the "next address" that was memorized, you check if that code (sequence) was better than what you have now in your alternate path. This is known as "delay" (or non-greedy) coding. Very abstract and messy, so you may not care to do it... Sorry if that last paragraph doesn't make much sense. What I'm trying to describe is a one-step look-ahead method. It has been demonstrated only 1-step look-ahead is sufficient to produce optimal results with a fixed encoding scheme (in other words Level 0, discussed above, does not change). (Also you could extend the idea to 2-step, 3-step, etc. look-ahead but it wouldn't improve anything.) I said "demonstrated" because I am not confident enough in information theory to say it have been rigoursly "proved." Actually you said the encoder is finalized, so I guess it doesn't matter. No worries (although it generally will improve most images a small amount and some images a lot, the cost [in programming effort and user run time] is serious). If you could post some images along with a report of the before and after file sizes, that would be cool. I *think* there are some nice source images in Tokra's VDC mode mania. But if that is not satisfactory (or need more), I have a billion and one images I could email to you or post here, if you would like. Of course, they won't all fit in a single email/post  |
|
|
|
Post by VDC 8x2 on Aug 28, 2014 7:53:02 GMT
I can tweak farcopy if we find results that warrant it.
|
|
|
|
Post by hydrophilic on Aug 29, 2014 6:44:26 GMT
Cool. Um, if your version of V.BASIC will allow, I ask you create a 32-bit version. Fortunately I do have one PC running 64 bit Windows, but the others are 32-bit. Maybe I am the only one on Earth still using 32-bit Windows? Considering this forum, I doubt it  It is really causing me edit-itis (that's medical terminology) to work with two PCs at once; my laptop with win64 and this desktop with win32. Enough with personal issues The first image I compressed (120 blocks) took about 30 seconds to compress the file (on a 64-bit Intel P6200 @ 2.13GHz). This was quite a shock to me because my video encoder usually does it in about 1 second, and it is not constrained to the last 2K.... my compressor searches all (48K) RAM... and that is on a 32-bit machine at 1.7GHz (to be fair, a "standard" [8x8 cells] VIC-II image is less than half the size of "enhanced" [8x2 cells] VDC image). Well I know Visual BASIC isn't as fast as C, but wow what a difference! Since you're not doing video, I guess 20 seconds isn't a big deal. I wonder how long it would take in BASIC 7 on the C128 After successfully compressing the first image, I did what you said, and tried LOAD/COMPRESS/SAVE for a second image. Well LOAD seemed to work, but it did not re-set the filled progress bar. No big deal, it did reset when I pressed COMPRESS... but then nothing happened (I waited about 20 minutes while I typed this in). I closed VDCompress and re-opened it and was able to compress the second image. If you have the time/motivation, you might want to look into reading arguments from the command line. That way it can be used in a batch file. The way I do apps like this is open a GUI if no arguments are given. Well I'm not sure how you'd not show a window in the new version of VB (sorry for the double negative)... that isn't really important I guess. As a bonus, the user would still get to see the progress bar ! Well the important thing is that your software works right now! Creating a nice UI (command line, GUI, or both) is another set of apples. Something many software authors neglect. Beleive me, I routinely work with HORRIBLY designed software. But only because it is work. At home I throw trash like that out. Umm... I'm not saying your UI is trash (it kind of reads like that). In fact, I love the simple design I use to love Google for the same reason, but in recent years they've become more bloated. Just saying it is rough around the edges, something I am sure you know, so I'll shut up now. EditSeveral files (umm 3) of the same size (120 blocks) all took about 30 seconds (each) to compress. A smaller (80 block) file took about 20 seconds. Well 4 files isn't a good average, but because I can't run it in batch mode, and the power on my laptop is running low, I don't have anything else to report at the moment. |
|
|
|
Post by VDC 8x2 on Aug 30, 2014 17:03:28 GMT
How did you handle your far copy in your program?
|
|
|
|
Post by hydrophilic on Aug 31, 2014 9:09:01 GMT
I have two versions: near and far. My near copy uses two bytes and is essentially identical to your far copy (i.e., distance around 1K and copy length only 8 or 16 bytes). My far copy version uses three bytes; it can reach forward or backward +/- 32768 bytes (so effectively it can reach any address) and can copy up to 64 bytes... as I recall, I don't have the source code on this PC. The only major difference is my video compressor searches forward in memory too (you are only searching backwards). I really don't think a forward search would apply for a single image. The closest thing I can think of would be a 'predefined' byte (or byte sequence)... this would need to be specified at the start of the file, and then you could assign some short code to reference it. For example zero could be the pre-defined value. Then whenever you need two bytes of zero (an RLE of 2, for example) you could use a short 1-byte code (you don't need to give the pre-defined value [zero] as a second byte). Of course the pre-defined value might be a multi-byte value. I'm not sure of the best way to determine a good (let alone optimal) pre-defined value (be it a single byte, or a multi-byte, value), but a simple method that gives good results is to do a second pass of the compressed code (before writing it out to a file). I will call this "optimization". I find in many (un-optimized) files that there will be several RLE / Copy codes that "almost" go in sequence ... but instead those sequences get interrupted by a simple/annoying 1-byte "raw" value (which means a two-byte "raw" code must be inserted between the RLE / Copy code sequences). If you can find a byte (or byte sequence) which occurs more than once in the file (where it interrupts RLE / Copy sequences), then using a pre-defined code will improve compression... I haven't played with pre-defined values much to say how it effective it is (or is not). This is because of my application... better results are gained (my opinion) from effective image generation (sloppy/lossy encoding) and re-using exisiting image buffers (which is why I search forward and backward). As far as speed, one method that greatly improves Copy is to build a table of byte pairs. Memorize the location (address in source file) of every used byte pair. There are 64K (256*256) possible byte-pairs (although many will not occur). This works because for "far" Copy to work (as opposed to "mirror copy") you need to find a byte-sequence that begins with the same two bytes you want to encode 'now' (i.e., two-byte minimum length). Using a table means you don't have to search very much. Just check all occurances of the current two bytes starting 'now'. Usually there will be (much) less than 100 candidates, so you test them to see which gives the longest copy length (obviously you can ignore any that are out-of-range [too far]). This is much faster than testing the last 1000 or 2000 bytes! (depending on bit-assignments for Copy.) For video, where searches go forward and backward, it works twice as well. EditJust wanted to add that the exact values used in my video encoder wouldn't be much interst anyway. They have been tweeked for VIC-II images and for the type of lossy image compression in use. In other words, the generic information I have given is really all you need. Also, before I said for Level 0 opitmization you need to update both V.BASIC encoder and C128 Decoder, this is not strictly true. For example, you can play around with different codes in V.BASIC (the encoder) until you find something that works well for most VDC images. When this is decided, then you update C128 Decoder. So eventually, both need to be updated, but in practice you really only need to tweek the encoder.... I guess the only exception would be when you are concerned with the decompression speed on the C128. For single images, I don't think this would ever be a serious factor. From my experience, you are running up against the limits of this simple byte-based encoding scheme. You can tweek the bit assignments for RLE / Copy, you might want to have two versions (2-byte and 3-byte) of "far" (non-mirror) copy, and you might want to use a pre-defined value(sequence). Even if you implement and tweak them all, it probably won't improve compression more than, say, 10% or 20%. Already I think your encoder works great for CG images... like Risen From Oblivion had the best compression of the images I tested (at an amazing 90% compression). I think it is fine if you want to use it for your Gold Box game conversion. If you want to make an "all-purpose" image compressor, then you would need something more complex. At least variable-length code sequences (known as entropy or Huffman encoding), and at the extreme, some image transform such as DCT like used in JPEG. So it really comes down to how much effort you want to invest, and how generic you want your compressor to be. Ummm... if you wanted to do something like DCT then the decoding speed of the C128 would become a serious factor  |
|
