{"id":2535,"date":"2010-06-06T15:49:11","date_gmt":"2010-06-06T22:49:11","guid":{"rendered":"http:\/\/multimedia.cx\/eggs\/?p=2535"},"modified":"2020-07-25T23:54:29","modified_gmt":"2020-07-26T06:54:29","slug":"understanding-the-vp8-token-tree","status":"publish","type":"post","link":"https:\/\/multimedia.cx\/eggs\/understanding-the-vp8-token-tree\/","title":{"rendered":"Understanding the VP8 Token Tree"},"content":{"rendered":"<p>I got tripped up on another part of the VP8 decoding process today. So I drew a picture to help myself understand it. Then I went back and read <a href=\"http:\/\/multimedia.cx\/eggs\/fighting-with-the-vp8-spec\/#comment-152057\">David Conrad&#8217;s comment<\/a> on my last post regarding <a href=\"http:\/\/multimedia.cx\/eggs\/fighting-with-the-vp8-spec\/\">my difficulty understanding the VP8 spec<\/a> and saw that he ran into the same problem. Since we both experienced the same hindrance in trying to sort out this matter, I thought I may as well publish the picture I drew.<\/p>\n<p>VP8 defines various trees for decoding different syntax elements. There is one tree for decoding the tokens and it is expressed in the VP8 spec as such:<\/p>\n<p><script src=\"https:\/\/gist.github.com\/multimediamike\/a6e49787bc93fd9cf4aff65dc526c639.js\"><\/script><\/p>\n<p>Here is what the table looks like when you make a tree out of it (click for full size image):<\/p>\n<p><center><br \/>\n<a href=\"http:\/\/multimedia.cx\/eggs\/wp-content\/uploads\/2010\/06\/vp8-token-graph.png\"><img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/multimedia.cx\/eggs\/wp-content\/uploads\/2010\/06\/vp8-token-graph-300x186.png\" alt=\"\" title=\"VP8 token graph\" width=\"300\" height=\"186\" class=\"aligncenter size-medium wp-image-2537\" srcset=\"https:\/\/multimedia.cx\/eggs\/wp-content\/uploads\/2010\/06\/vp8-token-graph-300x186.png 300w, https:\/\/multimedia.cx\/eggs\/wp-content\/uploads\/2010\/06\/vp8-token-graph-1024x637.png 1024w, https:\/\/multimedia.cx\/eggs\/wp-content\/uploads\/2010\/06\/vp8-token-graph.png 1175w\" sizes=\"auto, (max-width: 300px) 100vw, 300px\" \/><\/a><br \/>\n<\/center><\/p>\n<p>The catch is that it makes no sense for an end-of-block (EOB) token to follow a 0 token since EOB already indicates that the remainder of the coefficients should be 0 anyway. Thus, the spec states that, &#8220;decoding of certain DCT coefficients may skip the first branch, whose preceding coefficient is a DCT_0.&#8221; I confess, I didn&#8217;t understand what &#8220;skip the first branch&#8221; meant until I drew the tree.<\/p>\n<p><center><br \/>\n<img loading=\"lazy\" decoding=\"async\" src=\"http:\/\/multimedia.cx\/eggs\/wp-content\/uploads\/2010\/06\/vp8-token-graph-annotated.png\" alt=\"\" title=\"Annotated VP8 token graph\" width=\"399\" height=\"326\" class=\"aligncenter size-full wp-image-2536\" srcset=\"https:\/\/multimedia.cx\/eggs\/wp-content\/uploads\/2010\/06\/vp8-token-graph-annotated.png 399w, https:\/\/multimedia.cx\/eggs\/wp-content\/uploads\/2010\/06\/vp8-token-graph-annotated-300x245.png 300w\" sizes=\"auto, (max-width: 399px) 100vw, 399px\" \/><br \/>\n<\/center><\/p>\n<p>For those wondering why it might be sub-optimal (clarity-wise) for a spec to simply regurgitate vast chunks of C code, this makes a decent case. As you can see, the spec makes certain assumptions about how a binary tree should be organized in a static array (node <em>n<\/em> points to elements <em>n<\/em>*2 and <em>n<\/em>*2+1 as its branches; leaves are either negative or 0). This is the second method I have seen; another piece of code (not the VP8 spec) had the nodes in the first half of the array and pointed to leaves in the second half. There must be other arrangements.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>I had trouble understand this part of the VP8 spec; I drew a picture in case other people have the same difficulty<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[219],"tags":[],"class_list":["post-2535","post","type-post","status-publish","format-standard","hentry","category-vp8"],"aioseo_notices":[],"_links":{"self":[{"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/posts\/2535","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/comments?post=2535"}],"version-history":[{"count":13,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/posts\/2535\/revisions"}],"predecessor-version":[{"id":4646,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/posts\/2535\/revisions\/4646"}],"wp:attachment":[{"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/media?parent=2535"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/categories?post=2535"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/multimedia.cx\/eggs\/wp-json\/wp\/v2\/tags?post=2535"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}