Diary Of An x264 Developer

11/25/2010 (1:30 pm)

Patent skullduggery: Tandberg rips off x264 algorithm

Filed under: 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 M5 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.

61 Responses to “Patent skullduggery: Tandberg rips off x264 algorithm”

  1. nine Says:

    Thumbs down Tandberg. THUMBS DOWN!

  2. tobias3 Says:

    In Germany you can’t patent something that is publicly known, even if you published it yourself.

    Doesn’t the same hold for US Patents?

    This patent would be worthless here. You could just show the commit logs and thereby prove that the idea was public knowldege at the time. (You’d have to find that commit though).

  3. anty Says:

    Doesn’t this render any patent invalid, if you can prove that it was available to the public before the patent was filed?

  4. Yuhong Bao Says:

    Yea, hopefully the patent examiner can show that the commit was prior art.

  5. Chris Says:

    @anty, @tobias3 Yes, any concept that is in use by a competitor before the patent application renders it invalid. It is just a pain to deal with these situations.

  6. Relgoshan Says:

    Well if you want to permanently blacklist any of his future patent claims, try to trick him into filing on a cold-fusion patent.

  7. Ciaran O'Riordan Says:

    To the commenters: Yes, of course x264 can be used as prior art to block the application from being granted.

    This fraud will get stopped (I presume). How many other fraudulent patents have been acquired this way over the past years and are currently being used against software developers?

    Patents don’t work in domains where individuals and small businesses produce stuff on a scale that impacts the market. Software developers usually don’t have the resources (time, money, legal resources) to check and challenge patents.

  8. Bas Says:

    The only purpose for the US Patent system is to facilitate the appropriation of other people’s stuff for the big US companies (read: steal foreign people’s properties).
    I think this practice won’t ever stop until the US collapse.

  9. Greg Herlein Says:

    If this is true, you can halt the patent process via an in parte or ex parte review. They can apply for whatever they want. They may not get it. They won’t if you present evidence.

  10. smallstepforman Says:

    The US patent office grants patents for almost anything, and offloads verification to the Courts, which handle the actual investigation (if challenged). Just because a patent was issued, it doesn’t mean that it will be upheld in a Court of law. If the company requesting patents is stupid enough to finance this charade, what the hell, it’s their money. When they lose a court case, they will have to pay penalties to the other side, so it’s another money sink. All the other side needs to do is stick it out. I guess that’s another cost of running a business in the 21st century.

  11. Niobos Says:

    Under European law, this patent should not be granted. IIRC European patent law is “first to file”: The only date that matters is the date you file your patent request on. Since the idea was publicly available before the patent was requested, it is prior art.
    Under US law, this might not be the case. US patent law uses “first to invent”: If Tandberg can prove that they “invented” this algorithm before the commit got public, they can get the patent…

    I’m not a lawyer; this is just what I remember of my talk to a European patent reviewer.

  12. z Says:

    Contact the EFF – they will help you fight this bad-faith patent.

  13. Paul Johnson Says:

    I seem to recall that the US patent process includes an oath that this is your own invention. Prosecutions under this law are incredibly rare, but maybe this is sufficiently blatent to get someone to take an interest.

  14. Anonymous Says:

    Coincidence? On Slashdot today, yet another coder sees his open source project patented:

    http://slashdot.org/story/10/11/25/0416208/Coder-Accuses-IBM-of-Patenting-His-Work

  15. Paul Says:

    Similar issue, at Slashdot yesterday – a coder reports that IBM patented his open source code: http://slashdot.org/story/10/11/25/0416208/Coder-Accuses-IBM-of-Patenting-His-Work

  16. spc Says:

    I reckon You should definitely consult people from EFF and
    guys from Software Freedom Law Center.
    They can help, and they’ve got resources.

  17. Mick Says:

    This isn’t just with the software world, it happens with everyday patents too. A patent was awarded in the UK by a UK company for a very special and completely unique ‘vortex muffler’ design which was licenced to them and had been made for many years in Australia. The Australian company was very small (hence the licencing), and has since gone out of business due to the UK company, and don’t have the money for legal action (remember big companies = expensive ruthless lawyers). The UK company didn’t even pay for the licencing fees.

    The reason why I brought this up is because its the same kind of thing that has happen here, a patent was issued for something that clearly wasn’t theirs to patent, and it wasn’t just the principle that was stolen, it was the actual code itself. Whilst the patent may be classified as legal, there’s another nice little thing called copyright. Since the patent clearly and uncontestably violates the copyright of the original author, the patent is effectively useless.

    If you copy a paragraph out of book or any other text, without making a proper reference to it, you can be done for plagiarism. A persons writing, if it is their own, is technically automatically copyrighted.

    Since code is writing, just in a different language than English, it can be considered under the same law as any other writing. Therefore, Tandberg has openly violated the copyright of the code and submitted it as their own, they can be sued for copyright. They can also be sued for providing false information to the patent office, since to get a patent I believe it is required that a statement is given to the effect the item being patented is of their own work and design, and that it is unique.

    As Greg Herlein said, if Dark Shikari provided evidence that the patent is void, and they ignore it, he has every right to take it to the ombudsman (or whatever the oversee is in the US), or to his local congressman since thats what they’re there for, a representee for the people.

  18. Christian Abildsø Says:

    Just starting off, I’m posting this as me, and not on behalf of Tandberg/Cisco, so don’t take anything I say in any official capacity.

    I’m an employee in what was Tandberg, and is now part of Cisco. While I’m pretty new here, that sort of activity is certainly not representative of company policy or ethical standards within either company.

    I’m finding out who the right person to notify is, and sending a link to this post. What, if anything, happens beyond that, I don’t know, but assuming your claim is provably legitimate, I imagine something will.

  19. Angry Voter Says:

    Knowingly abusive patents need to be prosecuted as felony fraud.

  20. Florian Says:

    This kind of thing is gross systematic misconduct on the side of the patent office. The patent office has a stated duty to perform, for which they are funded with tax money.

    If this organization is incapable of correcting their course, the DOJ should halt their work with an injunction, an audit of their workforce, structure and procedures should be performed, and if this measures fail to rectify the situation, the office should be disbanded and the funds allocated to a successor organization capable of performing the job.

  21. y. leong Says:

    except it accost money and time to do such review

    even if you are aware of such theft!

  22. wisam Says:

    The playing field and strategy has certainly changed for Tandberg since Cisco bought them.

  23. v36ar Says:

    This is very bad of Tandberg. And they are now a part of Cisco. So watch out!

  24. Bern Says:

    So, why aren’t they potentially subject to severe sanctions for appropriating & attempting to patent someone else’s work?

    Assuming the commit log proves (in a legal sense) that the didn’t come up with the material, that is.

  25. Sam Cook Says:

    I think the trick with this is that even though their is prior art the patents are rarely fully checked so the only way to challenge this is in court. This means that lots of people with limited resources will be pushed out purely because they can’t afford to defend their prior art.

  26. Eric Says:

    Actually this looks like it might be a criminal offense as well.
    It looks like intetionally presenting someone else’s idea as your own should be considered fraudulant.

    The US patent office should upon disovery of these facts put them in the hands of a district attorny or something similar.

    Tandberg would be likely liable for possible civil claims by you (or your organization).

  27. Jason Says:

    Germany is a “first to file” country regarding patents, as opposed to the US which is “first to invent.” So they may still get the patent.

  28. Paul Says:

    I’m sorry for the loss of time you’ve had and will have over this. This only delays future x264 development :(

  29. Robert Says:

    Title 35 of the US
    Code, Section 102(g) prohibits
    anyone from getting a patent on
    something that he (or she) did
    not themselves invent. It would
    also violate Rule 56 of the Rules
    of Practice of the USPTO which
    requires those involved with the
    preparation and prosecution of a
    patent application to disclose to
    the USPTO any reason known why
    a patent should not issue. Failure
    to do so is called “inequitable
    conduct” and is a basis for finding
    the patent permanently
    unenforceable. In some cases it
    can also be a federal crime.
    The US is not a first-to-file country
    but a first-to-invent country. That
    means that it is possible for an
    inventor to get a patent even
    thought they were not the first
    one to file an application at the
    USPTO but were the first to invent
    and were diligent in efforts to
    obtain a patent. Copying of this
    type is serious indeed.
    Theoretically, conduct of this type
    could also be a copyright
    infringement.

  30. Dave Simon Says:

    And where the hell is law enforcement on this?! They have no problem spending millions to pursue .mp3 downloaders, but when someone’s IP is clearly stolen from them, law enforcement has an OBLIGATION to investigate and prosecute the offenders to the fullest extent of the law.

    These algoritms are clearly more valuable than a much of songs from a bunch of has been musicians.

    Mr District Attorney or Mr. U.S. Attorney… hello?

  31. Kevin Morton Says:

    software patents can be a grate tool and they were designed to help out the lital guy, but lawyers got in the way of that.

  32. Johnny Says:

    ” … In Germany you can’t patent something that is publicly known, even if you published it yourself. …”

    Nobody’s attempting to patent this in Germany. This is a submission to the USPTO. Because you have to patent country-by-country, most companies simply submit to the USPTO. Once you get the US patent, it’s essentially useless to others since they will never be able to sell product that is based on that patent in the USA. Similarly, failure to obtain the US patent prevents you from selling in the US, even if you have a foreign patent.
    There’s a bit more to it … but the short answer is you can use the US patent to defend yourself in those other countries (eg to get a competing patent invalidated).

  33. Eric Says:

    The US Patent Examiner will likely throw this out as prior art. To be safe, follow everything that is going on with it on the public PAIR portal:

    http://portal.uspto.gov/external/portal/pair

    you will need the application serial number (12649764) and you will be able to see all of the correspondence between the Patent Office Examiner (including contact info) and Tandberg.

    Searches on Google are a standard part of the prior art search in the USPTO. Make sure statements by you show up in google results when phrases from the claims are searched for. I would do a text copy of all of the claims (or the whole application) and put it in a post on this site along with your statement that it is all prior art. It is incredibly unlikely the patent examiner won’t find the prior art, but there are things you can do to make sure just in case. Good luck

  34. devilworld Says:

    Look, you might have to go to court for this. On the bright side, you can counter-suit him for the entire cost of the court proceedings, like hiring a lawyer etc., and also for FUD damages to the open-source community.

    Make an example of this turd.

    also, just to be proactive, make sure you email the patent office with proof that their patenting attempt was public before they ever thought of filing a patent. the examiner might miss something

  35. lovecraft Says:

    >I think this practice won’t ever stop until the US collapse

    well then, looks like things are looking up!

  36. wtay Says:

    It could also be that the two similar ideas were simply developed independently. It usually takes a while before a patent is filed, maybe the algorithm was even developed and working much before that.

    An official statement in an article
    (http://www.digi.no/856986/anklager-tandberg-for-video-patentjuks , use google translate) seems to support this. It also says that the patent and x264 code is rather different.

    Maybe this blogpost is overreacting just a little. Wouldn’t be the first time that happened, actually.

  37. Dave B Says:

    Stop suggsting passive agressive methods. If the patent hasn’t been granted, write to the US Patent officee, cite the patent number, then explain your case why the patent shouldn’t be granted. As for law enforcement, at this point you have a civil matter. Once the USPTO is actively made aware of the situation, a criminal investigation might begin.

  38. m3kw Says:

    So, tell us what are you going to do about it.

  39. Dark Shikari Says:

    @m3kw

    Probably file a complaint with the USPTO about it. Lawsuits/etc are stupid and a waste of development time and money.

  40. Matt Says:

    are you joking? don’t blame the developer? You think the developer couldn’t have possibly seen this coming?

  41. anonymous coward Says:

    Hi,

    ever thought about that Tandberg might just be trying to protect their own ass against something we don’t know ? Or somebody did something just flat stupid ? The whole thing turns evil at the point were a patent is used to sue companies in a pointless and unfair fashion just to rip off some money. If that is not the case, why complain ? That patent would not withstand any appeal anyway.

    By the way, private people can’t be sued because of patent infringements. Only profit making companies can be sued. Many OpenSource posers (sorry, there is just to much hype in there; I also write open source software myself) just do not have a clue and keep complaining against nonexistent threats. I did that mistake by myself in the past. Its better to actually spend some time to acquire the necessary knowledge to be able to judge the situation appropriately.

    So, you as a private hacker first of all have nothing to fear. If your business depends on that patent, well I guess that you lucky one just got the jackpot :D There are many lawyers out there that will file that infringement for you with pleasure.

    Cheers

  42. anonymous coward Says:

    Oops, sorry, replace “file that infringement” by “file that complaint”

  43. some guy Says:

    Tandberg is now part of cisco

  44. Rich Says:

    It will be interesting to see how this comes out. There are patents on the original H.264 algorithms, and if I understand correctly the only reason we have x264 is that it is developed in Europe where the software patents on H.264 are not enforceable.

    It seems to me, therefore, that what Tandberg requests to patent is a compatible implementation of an existing, patented algorithm.

  45. phayes Says:

    “There’s been a lot of very obnoxious misuse of software patents in recent years. This ranges from patent trolls…”

    But hardly unexpected and I think it is quite wrong to single out and blame a subset of /legitimate/ patent holders and/or their “bad” patents for patent system-intrinsic negative effects which the exercising of legitimate patent rights *naturally* entail. What you see as “obnoxious misuse” is what patent system economists and historians would recognise as part of the normal operation of the patent system. Patents confer powerful rights of exclusion by design, and it’s unfair to express moral outrage when those rights are exploited in ways you don’t happen to like. If you believe that patent eligibility for software is economically justifiable (I certainly don’t) then you have to accept the consequences.

  46. Lawrence D’Oliveiro Says:

    Independent invention is not accepted as a defence for patent infringement. So why should it be acceptable as a justification for granting the patent in the first place?

  47. Law Student Says:

    If I was the examiner this is an easy rejection under 102(a) and 102(b) (novelty + statutory bars). Likewise, I would throw in a 103 rejection for nonobviousness. If you could actually prove these people weren’t the inventors you could reject under 102(f), but that is rarely used, because the inventors are required to file an affidavit that says they invented, which is nearly impossible to rebut without actually going to court and through discovery. If this patent actually were to issue, I would put it into immediate re-exam and get this thing rejected. People at the USPTO are smarter than you think, this should be an easy rejection.

  48. Dave Says:

    Its entirely possible that this is a cleanroom re-implementation *because* of the way the system works.

    Tanberg may well have employed deliberately programmers and system designers not familiar with the field, and instructed them to avoid referencing published standards and/or existing code, in order to avoid any accusations that the resulting product was “tainted” by the prior knowledge of existing standards. This would be a stupid move, but being stupid isn’t the same as being criminal :)

  49. I.P.Friely Says:

    Well if you didn’t want the guy to be harassed you wouldn’t have mentioned him in your blog, surely you realize that portion of your user base are sociopaths.

  50. Heph Says:

    @matt: The Developer may had indeed no clue. He might have come up with the idea and the companie might have said “Ok sure sounds good let our law-department check that first though.”

    If now that department or someone other made a failure by bad research its not the developer that had aactualy a genuine idea.

  51. CruNcher Says:

    They claim they have prior art since March 2008 so 9 months before Dark made his public in December 2008 that looks bad.

  52. CruNcher Says:

    I wonder if more are gonna wakeup now and stake their claims vs x264 now it gone commercial when i talked to someone about this he clearly said x264 is no problem it doesn’t get in our way as it isn’t commercial now this has changed a bit and i guess many are currently shaking their shoes and aren’t happy with this commercial development.

  53. Chris Says:

    Searching other granted patents and journal articles etc for invalidating prior art is possible, but searching through all the software repositories around the world is (IMHO) just not feasible for one or a few examiners.

    From the USPTO website, a new pilot of a peer-review program has recently started to help examiners find prior art for new applications. Hopefully this becomes standard procedure in future.

  54. Jan Wildeboer Says:

    Hi Jason,

    I have updated my blog entry at http://jan.wildeboer.net/2010/11/patent-madness-by-tandberg/ to reflect your updates.

    BTW – being named as harrassing the Tandberg engineer isalso not that nice, Wasn’t my intention. I wanted to present both sides, the patent (and his “inventor”) and your arguments.

    Jan Wildeboer

  55. Herve Says:

    @wtay: That Tandberg may have discovered the algorithm independently does not make their patent more valid. They have filed it after the corresponding x264 code was made public, so they can’t claim they are inventing anything. Tandberg claim that they developed internally the feature long before they filed the patent, but it’s absolutely not provable, and it can not be used as evidence by them. What is not published does not exist, in the patent world.

  56. Herve Says:

    @CruNcher: don’t change the story. Tandberg is accused of stealing code from x264, not the other way around. Saying: “wonder if more are gonna wakeup now and stake their claims vs x264″ is a strange and partial way of presenting things.

  57. Herve Says:

    @wtay: FYI, 2 months is largely enough to file patent. What is long is not the filing itself, it’s the time for the patent to be granted by USPTO.

  58. Lars Says:

    Tandberg now belongs to Cisco, and Cisco was quite good at ripping off Linux and the GPL, so Tandberg is now in the hands of experts.

  59. Bill Riemers Says:

    The truth is most software patents are bogus, and most claims are paid out of court. Even if a patent is completely bogus, it can cost millions of dollars to fight a patent claim. Quite frankly, unless you are sueing a fortune 500 company, you can expect them to settle on the case. Really, your best strategy when writing open source is to try and get it incorporated into a distribution like Red Hat Enterprise Linux, so you have a company that will fight to protect their customers, and hence your code.

  60. Rufus Polson Says:

    It might be amusing to pursue the copyright angle and accuse them of software piracy. If you accuse them of being a bunch of dirty file copiers, you can probably get their ISPs to cut off their internet access and so forth without ever hitting a courtroom.

  61. Tomas Arce Says:

    IT IS SHAMEFUL for programmers to participate in patents. Having a name in a patent should be looked by peers as a disgrace and a selfish act. Yes it serves you in the short run but you end up hurting the rest of us. The fact is that software like any evolutionary process is based on iteration and incremental improvements. If you cut this process you are cutting the way things naturally evolve. This is not good for anyone. Been the first should be paid back with recognition not with law enforcement.

    A better world does not just happen it must be made.

Leave a Reply