Recherche avancée

Sur d’autres sites (6213)

• Patent skullduggery : Tandberg rips off x264 algorithm

  25 novembre 2010, par Dark Shikari — patents, ripoffs, x264

  Update : Tandberg claims they came up with the algorithm independently : to be fair, I can actually believe this to some extent, as I think the algorithm is way too obvious to be patented. Of course, they also claim that the algorithm isn’t actually identical, since they don’t want to lose their patent application.

  I still don’t trust them, but it’s possible it’s merely bad research (and thus being unaware of prior art) as opposed to anything malicious. Furthermore, word from within their office suggests they’re quite possibly being honest : supposedly the development team does not read x264 code at all. So this might just all be very bad luck.

  Regardless, the patent is still complete tripe, and should never have been filed.
  

  Most importantly, stop harassing the guy whose name is on the patent (Lars) : he’s just a programmer, not the management or lawyers responsible for filing the patent. This is stupid and unnecessary. I’ve removed the original post because of this ; it can be found here for those who want to read it.

  Appendix : the details of the patent :

  I figure I’ll go over the exact correspondence between the patent and my code here.

  1. A method for calculating run and level representations of quantized transform coefficients representing pixel values included in a block of a video picture, the method comprising :

  Translation : It’s a run-level coder.

  packing, at a video processing apparatus, each quantized transform coefficients in a value interval [Max, Min] by setting all quantized transform coefficients greater than Max equal to Max, and all quantized transform coefficients less than Min equal to Min

  The quantized coefficients are clipped to a certain valid range to allow them to be packed into bytes (they start as 16-bit values).

  reordering, at the video processing apparatus, the quantized transform ID coefficients according to a predefined order depending on respective positions in the block resulting in an array C of reordered quantized transform coefficients

  This is the zigzag pattern used in H.264 (and most formats) for reordering DCT coefficients. In x264, this is done before the run-level coder ste.

  masking, at the video processing apparatus, C by generating an array M containing ones in positions corresponding to positions of C having non-zero values, and zeros in positions corresponding to positions of C having zero values

  This is creating a bitmask based on the coefficient values, the pmovmskb step.

  is generating, at the video processing apparatus, for each position containing a one in M, a run and a level representation by setting the level value equal to an occurring value in a corresponding position of C ; and setting, at the video processing apparatus, for each position containing a one in M₅ the run value equal to the number of proceeding positions relative to a current position in M since a previous occurrence of one in M.

  This is the process of creating run/level values from the bitmask.

  Now into the detailed claims :

  2. The method according to Claim 1, wherein the masking further includes, creating an array C from C where positions corresponding to positions of nonzero values in C are filled with ones, and positions corresponding to positions of zero values in C are filled with zeros, and creating M from C by extracting the most significant bit from values in respective position of C and inserting the bits in corresponding positions in M.

  They’re extracting the most significant bit of the values to create a bitmask. This is exactly what the pmovmskb in my algorithm does.

  3. The method according to Claim 2, wherein the creating of the array C is executed by a C++ function PCMPGTB, and the creating of M from C is executed by a C++ function PMOVMSKB.

  And here they use pcmpgtb (they call it a C++ function for some reason, but it’s a SSE instruction) to do the clipping of the input values. This is exactly the same method I used in decimate_score. They also use pmovmskb as mentioned.

  4. The method according to Claim 1 , wherein the generating of the run and level representation further includes determining positions containing non-zero values in C by corresponding positions containing ones in M.

  5. The method according to Claim 4, wherein the determining of positions containing non-zero values in C is executed by a C++ function BSF.

  Here they iterate over the bitmask of transform coefficients using a “BSF” function to find runs, which is exactly what I did. Of course, BSF isn’t a function, it’s an x86 instruction.

  6. The method according to Claim 1 , wherein Max is 256 and Min is 0.

  This is almost surely a typo or mistake of some sort. They mean the Max should be 255, not 256 : 256 doesn’t fit in a uint8_t.

  7. The method according to Claim 1 , wherein the predefined order follows a zigzag path of transform coefficient positions in the block starting in an upper left corner heading towards a lower right corner.

  This is a description of the typical DCT zigzag pattern (like in H.264, MPEG-2, Theora, etc).

  Everything after this part is just repeating itself with the phrase “an apparatus” added in order to make the USPTO listen to them.

• The 11th Hour RoQ Variation

  12 avril 2012, par Multimedia Mike — Game Hacking, dreamroq, Reverse Engineering, roq, Vector Quantization

  I have been looking at the RoQ file format almost as long as I have been doing practical multimedia hacking. However, I have never figured out how the RoQ format works on The 11th Hour, which was the game for which the RoQ format was initially developed. When I procured the game years ago, I remember finding what appeared to be RoQ files and shoving them through the open source decoders but not getting the right images out.

  I decided to dust off that old copy of The 11th Hour and have another go at it.

  
  
  

  Baseline
  The game consists of 4 CD-ROMs. Each disc has a media/ directory that has a series of files bearing the extension .gjd, likely the initials of one Graeme J. Devine. These are resource files which are merely headerless concatenations of other files. Thus, at first glance, one file might appear to be a single RoQ file. So that’s the source of some of the difficulty : Sending an apparent RoQ .gjd file through a RoQ player will often cause the program to complain when it encounters the header of another RoQ file.

  I have uploaded some samples to the usual place.

  However, even the frames that a player can decode (before encountering a file boundary within the resource file) look wrong.

  Investigating Codebooks Using dreamroq
  I wrote dreamroq last year– an independent RoQ playback library targeted towards embedded systems. I aimed it at a gjd file and quickly hit a codebook error.

  RoQ is a vector quantizer video codec that maintains a codebook of 256 2×2 pixel vectors. In the Quake III and later RoQ files, these are transported using a YUV 4:2:0 colorspace– 4 Y samples, a U sample, and a V sample to represent 4 pixels. This totals 6 bytes per vector. A RoQ codebook chunk contains a field that indicates the number of 2×2 vectors as well as the number of 4×4 vectors. The latter vectors are each comprised of 4 2×2 vectors.

  Thus, the total size of a codebook chunk ought to be (# of 2×2 vectors) * 6 + (# of 4×4 vectors) * 4.

  However, this is not the case with The 11th Hour RoQ files.

  Longer Codebooks And Mystery Colorspace
  Juggling the numbers for a few of the codebook chunks, I empirically determined that the 2×2 vectors are represented by 10 bytes instead of 6. Now I need to determine what exactly these 10 bytes represent.

  I should note that I suspect that everything else about these files lines up with successive generations of the format. For example if a file has 640×320 resolution, that amounts to 40×20 macroblocks. dreamroq iterates through 40×20 8×8 blocks and precisely exhausts the VQ bitstream. So that all looks valid. I’m just puzzled on the codebook format.

  Here is an example codebook dump :
  

  ID 0x1002, len = 0x0000014C, args = 0x1C0D
    0 : 00 00 00 00 00 00 00 00 80 80
    1 : 08 07 00 00 1F 5B 00 00 7E 81
    2 : 00 00 15 0F 00 00 40 3B 7F 84
    3 : 00 00 00 00 3A 5F 18 13 7E 84
    4 : 00 00 00 00 3B 63 1B 17 7E 85
    5 : 18 13 00 00 3C 63 00 00 7E 88
    6 : 00 00 00 00 00 00 59 3B 7F 81
    7 : 00 00 56 23 00 00 61 2B 80 80
    8 : 00 00 2F 13 00 00 79 63 81 83
    9 : 00 00 00 00 5E 3F AC 9B 7E 81
    10 : 1B 17 00 00 B6 EF 77 AB 7E 85
    11 : 2E 43 00 00 C1 F7 75 AF 7D 88
    12 : 6A AB 28 5F B6 B3 8C B3 80 8A
    13 : 86 BF 0A 03 D5 FF 3A 5F 7C 8C
    14 : 00 00 9E 6B AB 97 F5 EF 7F 80
    15 : 86 73 C8 CB B6 B7 B7 B7 85 8B
    16 : 31 17 84 6B E7 EF FF FF 7E 81
    17 : 79 AF 3B 5F FC FF E2 FF 7D 87
    18 : DC FF AE EF B3 B3 B8 B3 85 8B
    19 : EF FF F5 FF BA B7 B6 B7 88 8B
    20 : F8 FF F7 FF B3 B7 B7 B7 88 8B
    21 : FB FF FB FF B8 B3 B4 B3 85 88
    22 : F7 FF F7 FF B7 B7 B9 B7 87 8B
    23 : FD FF FE FF B9 B7 BB B7 85 8A
    24 : E4 FF B7 EF FF FF FF FF 7F 83
    25 : FF FF AC EB FF FF FC FF 7F 83
    26 : CC C7 F7 FF FF FF FF FF 7F 81
    27 : FF FF FE FF FF FF FF FF 80 80
  

  Note that 0x14C (the chunk size) = 332, 0x1C and 0x0D (the chunk arguments — count of 2×2 and 4×4 vectors, respectively) are 28 and 13. 28 * 10 + 13 * 4 = 332, so the numbers check out.

  Do you see any patterns in the codebook ? Here are some things I tried :

  • Treating the last 2 bytes as U & V and treating the first 4 as the 4 Y samples :
    
    
    
  • Treating the last 2 bytes as U & V and treating the first 8 as 4 16-bit little-endian Y samples :
    
    
    
  • Disregarding the final 2 bytes and treating the first 8 bytes as 4 RGB565 pixels (both little- and big-endian, respectively, shown here) :
    
    
    
  • Based on the type of data I’m seeing in these movies (which appears to be intended as overlays), I figured that some of these bits might indicate transparency ; here is 15-bit big-endian RGB which disregards the top bit of each pixel :
    
    
    

  These images are taken from the uploaded sample bdpuz.gjd, apparently a component of the puzzle represented in this screenshot.

  Unseen Types
  It has long been rumored that early RoQ files could contain JPEG images. I finally found one such specimen. One of the files bundled early in the uploaded fhpuz.gjd sample contains a JPEG frame. It’s a standard JFIF file and can easily be decoded after separating the bytes from the resource using ‘dd’. JPEGs serve as intraframes in the coding scheme, with successive RoQ frames moving objects on top.

  However, a new chunk type showed up as well, one identified by 0×1030. I have never encountered this type. Where could I possibly find data about this ? Fortunately, iD Games recently posted all of their open sourced games at Github. Reading through the code for their official RoQ decoder, I see that this is called a RoQ_PACKET. The name and the code behind it are both supremely unhelpful. The code is basically a no-op. The payloads of the various RoQ_PACKETs from one sample are observed to be either 8784, 14752, or 14760 bytes in length. It’s very likely that this serves the same purpose as the JPEG intraframes.

  Other Tidbits
  I read through the readme.txt on the first game disc and found this nugget :

          g)      Animations displayed normally or in SPOOKY MODE
                  SPOOKY MODE is blue-tinted grayscale with color cursors, puzzle
  
                  and game pieces.  It is the preferred display setting of the
  
                  developers at Trilobyte.  Just for fun, try out the SPOOKY
  
                  MODE.
  

  The MobyGames screenshot page has a number of screenshots labeled as being captured in spooky mode. Color tricks ?

  Meanwhile, another twist arose as I kept tweaking dreamroq to deal with more RoQ weirdness : After modifying my dreamroq code to handle these 10-byte vectors, it eventually chokes on another codebook. These codebooks happen to have 6-byte vectors again ! Fortunately, I was already working on a scheme to automatically detect which codebook is in play (plugging the numbers into a formula and seeing which vector size checks out).

• Best Overall FFMPEG FLV Quality

  23 janvier 2012, par dcolumbus

  First of all, FFMPEG has the worst documentation of all time... secondly, the syntax is so trivial that it's hard to understand what some lines are doing.

  What I'm looking to accomplish is the best quality FLV with the lowest file size. After all, isn't that everyone's goal ? These video will be streamed if that makes a difference.

  Perhaps some of you have command lines that do just this... for now, my video are no wider than 320... some are widescreen and so their heights are little smaller than 240.

  As it stands, the quality of the converted FLV's are quite poor...

  -i video.mov -ar 22050 -ab 32 -f flv -s 320x240 -aspect 4:3 video.flv