{"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":[],"aioseo_head":"\n\t\t<!-- All in One SEO 4.9.10 - aioseo.com -->\n\t<meta name=\"description\" content=\"I had trouble understand this part of the VP8 spec; I drew a picture in case other people have the same difficulty\" \/>\n\t<meta name=\"robots\" content=\"max-image-preview:large\" \/>\n\t<meta name=\"author\" content=\"Multimedia Mike\"\/>\n\t<link rel=\"canonical\" href=\"https:\/\/multimedia.cx\/eggs\/understanding-the-vp8-token-tree\/\" \/>\n\t<meta name=\"generator\" content=\"All in One SEO (AIOSEO) 4.9.10\" \/>\n\t\t<meta property=\"og:locale\" content=\"en_US\" \/>\n\t\t<meta property=\"og:site_name\" content=\"Breaking Eggs And Making Omelettes | Topics On Multimedia Technology and Reverse Engineering\" \/>\n\t\t<meta property=\"og:type\" content=\"article\" \/>\n\t\t<meta property=\"og:title\" content=\"Understanding the VP8 Token Tree | Breaking Eggs And Making Omelettes\" \/>\n\t\t<meta property=\"og:description\" content=\"I had trouble understand this part of the VP8 spec; I drew a picture in case other people have the same difficulty\" \/>\n\t\t<meta property=\"og:url\" content=\"https:\/\/multimedia.cx\/eggs\/understanding-the-vp8-token-tree\/\" \/>\n\t\t<meta property=\"article:published_time\" content=\"2010-06-06T22:49:11+00:00\" \/>\n\t\t<meta property=\"article:modified_time\" content=\"2020-07-26T06:54:29+00:00\" \/>\n\t\t<meta name=\"twitter:card\" content=\"summary\" \/>\n\t\t<meta name=\"twitter:title\" content=\"Understanding the VP8 Token Tree | Breaking Eggs And Making Omelettes\" \/>\n\t\t<meta name=\"twitter:description\" content=\"I had trouble understand this part of the VP8 spec; I drew a picture in case other people have the same difficulty\" \/>\n\t\t<script type=\"application\/ld+json\" class=\"aioseo-schema\">\n\t\t\t{\"@context\":\"https:\\\/\\\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/understanding-the-vp8-token-tree\\\/#article\",\"name\":\"Understanding the VP8 Token Tree | Breaking Eggs And Making Omelettes\",\"headline\":\"Understanding the VP8 Token Tree\",\"author\":{\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/author\\\/multimedia-mike\\\/#author\"},\"publisher\":{\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/#organization\"},\"image\":{\"@type\":\"ImageObject\",\"url\":\"http:\\\/\\\/multimedia.cx\\\/eggs\\\/wp-content\\\/uploads\\\/2010\\\/06\\\/vp8-token-graph-300x186.png\",\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/understanding-the-vp8-token-tree\\\/#articleImage\"},\"datePublished\":\"2010-06-06T15:49:11-07:00\",\"dateModified\":\"2020-07-25T23:54:29-07:00\",\"inLanguage\":\"en-US\",\"commentCount\":3,\"mainEntityOfPage\":{\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/understanding-the-vp8-token-tree\\\/#webpage\"},\"isPartOf\":{\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/understanding-the-vp8-token-tree\\\/#webpage\"},\"articleSection\":\"VP8\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/understanding-the-vp8-token-tree\\\/#breadcrumblist\",\"itemListElement\":[{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs#listItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\\\/\\\/multimedia.cx\\\/eggs\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/category\\\/vp8\\\/#listItem\",\"name\":\"VP8\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/category\\\/vp8\\\/#listItem\",\"position\":2,\"name\":\"VP8\",\"item\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/category\\\/vp8\\\/\",\"nextItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/understanding-the-vp8-token-tree\\\/#listItem\",\"name\":\"Understanding the VP8 Token Tree\"},\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs#listItem\",\"name\":\"Home\"}},{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/understanding-the-vp8-token-tree\\\/#listItem\",\"position\":3,\"name\":\"Understanding the VP8 Token Tree\",\"previousItem\":{\"@type\":\"ListItem\",\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/category\\\/vp8\\\/#listItem\",\"name\":\"VP8\"}}]},{\"@type\":\"Organization\",\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/#organization\",\"name\":\"Breaking Eggs And Making Omelettes\",\"description\":\"Topics On Multimedia Technology and Reverse Engineering\",\"url\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/\"},{\"@type\":\"Person\",\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/author\\\/multimedia-mike\\\/#author\",\"url\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/author\\\/multimedia-mike\\\/\",\"name\":\"Multimedia Mike\",\"image\":{\"@type\":\"ImageObject\",\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/understanding-the-vp8-token-tree\\\/#authorImage\",\"url\":\"https:\\\/\\\/secure.gravatar.com\\\/avatar\\\/2eb93f7cada658f7986b5092062849fa255779eada3342c8f6b9a40764b95fdd?s=96&d=identicon&r=g\",\"width\":96,\"height\":96,\"caption\":\"Multimedia Mike\"}},{\"@type\":\"WebPage\",\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/understanding-the-vp8-token-tree\\\/#webpage\",\"url\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/understanding-the-vp8-token-tree\\\/\",\"name\":\"Understanding the VP8 Token Tree | Breaking Eggs And Making Omelettes\",\"description\":\"I had trouble understand this part of the VP8 spec; I drew a picture in case other people have the same difficulty\",\"inLanguage\":\"en-US\",\"isPartOf\":{\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/#website\"},\"breadcrumb\":{\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/understanding-the-vp8-token-tree\\\/#breadcrumblist\"},\"author\":{\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/author\\\/multimedia-mike\\\/#author\"},\"creator\":{\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/author\\\/multimedia-mike\\\/#author\"},\"datePublished\":\"2010-06-06T15:49:11-07:00\",\"dateModified\":\"2020-07-25T23:54:29-07:00\"},{\"@type\":\"WebSite\",\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/#website\",\"url\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/\",\"name\":\"Breaking Eggs And Making Omelettes\",\"description\":\"Topics On Multimedia Technology and Reverse Engineering\",\"inLanguage\":\"en-US\",\"publisher\":{\"@id\":\"https:\\\/\\\/multimedia.cx\\\/eggs\\\/#organization\"}}]}\n\t\t<\/script>\n\t\t<!-- All in One SEO -->\n\n","aioseo_head_json":{"title":"Understanding the VP8 Token Tree | Breaking Eggs And Making Omelettes","description":"I had trouble understand this part of the VP8 spec; I drew a picture in case other people have the same difficulty","canonical_url":"https:\/\/multimedia.cx\/eggs\/understanding-the-vp8-token-tree\/","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/multimedia.cx\/eggs\/understanding-the-vp8-token-tree\/#article","name":"Understanding the VP8 Token Tree | Breaking Eggs And Making Omelettes","headline":"Understanding the VP8 Token Tree","author":{"@id":"https:\/\/multimedia.cx\/eggs\/author\/multimedia-mike\/#author"},"publisher":{"@id":"https:\/\/multimedia.cx\/eggs\/#organization"},"image":{"@type":"ImageObject","url":"http:\/\/multimedia.cx\/eggs\/wp-content\/uploads\/2010\/06\/vp8-token-graph-300x186.png","@id":"https:\/\/multimedia.cx\/eggs\/understanding-the-vp8-token-tree\/#articleImage"},"datePublished":"2010-06-06T15:49:11-07:00","dateModified":"2020-07-25T23:54:29-07:00","inLanguage":"en-US","commentCount":3,"mainEntityOfPage":{"@id":"https:\/\/multimedia.cx\/eggs\/understanding-the-vp8-token-tree\/#webpage"},"isPartOf":{"@id":"https:\/\/multimedia.cx\/eggs\/understanding-the-vp8-token-tree\/#webpage"},"articleSection":"VP8"},{"@type":"BreadcrumbList","@id":"https:\/\/multimedia.cx\/eggs\/understanding-the-vp8-token-tree\/#breadcrumblist","itemListElement":[{"@type":"ListItem","@id":"https:\/\/multimedia.cx\/eggs#listItem","position":1,"name":"Home","item":"https:\/\/multimedia.cx\/eggs","nextItem":{"@type":"ListItem","@id":"https:\/\/multimedia.cx\/eggs\/category\/vp8\/#listItem","name":"VP8"}},{"@type":"ListItem","@id":"https:\/\/multimedia.cx\/eggs\/category\/vp8\/#listItem","position":2,"name":"VP8","item":"https:\/\/multimedia.cx\/eggs\/category\/vp8\/","nextItem":{"@type":"ListItem","@id":"https:\/\/multimedia.cx\/eggs\/understanding-the-vp8-token-tree\/#listItem","name":"Understanding the VP8 Token Tree"},"previousItem":{"@type":"ListItem","@id":"https:\/\/multimedia.cx\/eggs#listItem","name":"Home"}},{"@type":"ListItem","@id":"https:\/\/multimedia.cx\/eggs\/understanding-the-vp8-token-tree\/#listItem","position":3,"name":"Understanding the VP8 Token Tree","previousItem":{"@type":"ListItem","@id":"https:\/\/multimedia.cx\/eggs\/category\/vp8\/#listItem","name":"VP8"}}]},{"@type":"Organization","@id":"https:\/\/multimedia.cx\/eggs\/#organization","name":"Breaking Eggs And Making Omelettes","description":"Topics On Multimedia Technology and Reverse Engineering","url":"https:\/\/multimedia.cx\/eggs\/"},{"@type":"Person","@id":"https:\/\/multimedia.cx\/eggs\/author\/multimedia-mike\/#author","url":"https:\/\/multimedia.cx\/eggs\/author\/multimedia-mike\/","name":"Multimedia Mike","image":{"@type":"ImageObject","@id":"https:\/\/multimedia.cx\/eggs\/understanding-the-vp8-token-tree\/#authorImage","url":"https:\/\/secure.gravatar.com\/avatar\/2eb93f7cada658f7986b5092062849fa255779eada3342c8f6b9a40764b95fdd?s=96&d=identicon&r=g","width":96,"height":96,"caption":"Multimedia Mike"}},{"@type":"WebPage","@id":"https:\/\/multimedia.cx\/eggs\/understanding-the-vp8-token-tree\/#webpage","url":"https:\/\/multimedia.cx\/eggs\/understanding-the-vp8-token-tree\/","name":"Understanding the VP8 Token Tree | Breaking Eggs And Making Omelettes","description":"I had trouble understand this part of the VP8 spec; I drew a picture in case other people have the same difficulty","inLanguage":"en-US","isPartOf":{"@id":"https:\/\/multimedia.cx\/eggs\/#website"},"breadcrumb":{"@id":"https:\/\/multimedia.cx\/eggs\/understanding-the-vp8-token-tree\/#breadcrumblist"},"author":{"@id":"https:\/\/multimedia.cx\/eggs\/author\/multimedia-mike\/#author"},"creator":{"@id":"https:\/\/multimedia.cx\/eggs\/author\/multimedia-mike\/#author"},"datePublished":"2010-06-06T15:49:11-07:00","dateModified":"2020-07-25T23:54:29-07:00"},{"@type":"WebSite","@id":"https:\/\/multimedia.cx\/eggs\/#website","url":"https:\/\/multimedia.cx\/eggs\/","name":"Breaking Eggs And Making Omelettes","description":"Topics On Multimedia Technology and Reverse Engineering","inLanguage":"en-US","publisher":{"@id":"https:\/\/multimedia.cx\/eggs\/#organization"}}]},"og:locale":"en_US","og:site_name":"Breaking Eggs And Making Omelettes | Topics On Multimedia Technology and Reverse Engineering","og:type":"article","og:title":"Understanding the VP8 Token Tree | Breaking Eggs And Making Omelettes","og:description":"I had trouble understand this part of the VP8 spec; I drew a picture in case other people have the same difficulty","og:url":"https:\/\/multimedia.cx\/eggs\/understanding-the-vp8-token-tree\/","article:published_time":"2010-06-06T22:49:11+00:00","article:modified_time":"2020-07-26T06:54:29+00:00","twitter:card":"summary","twitter:title":"Understanding the VP8 Token Tree | Breaking Eggs And Making Omelettes","twitter:description":"I had trouble understand this part of the VP8 spec; I drew a picture in case other people have the same difficulty"},"aioseo_meta_data":{"post_id":"2535","title":null,"description":null,"keywords":null,"keyphrases":null,"primary_term":null,"canonical_url":null,"og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"location":null,"local_seo":null,"breadcrumb_settings":null,"limit_modified_date":false,"ai":null,"created":"2020-12-31 21:55:31","updated":"2025-12-31 19:30:54","seo_analyzer_scan_date":null},"aioseo_breadcrumb":"<div class=\"aioseo-breadcrumbs\"><span class=\"aioseo-breadcrumb\">\n\t\t\t<a href=\"https:\/\/multimedia.cx\/eggs\" title=\"Home\">Home<\/a>\n\t\t<\/span><span class=\"aioseo-breadcrumb-separator\">&raquo;<\/span><span class=\"aioseo-breadcrumb\">\n\t\t\t<a href=\"https:\/\/multimedia.cx\/eggs\/category\/vp8\/\" title=\"VP8\">VP8<\/a>\n\t\t<\/span><span class=\"aioseo-breadcrumb-separator\">&raquo;<\/span><span class=\"aioseo-breadcrumb\">\n\t\t\tUnderstanding the VP8 Token Tree\n\t\t<\/span><\/div>","aioseo_breadcrumb_json":[{"label":"Home","link":"https:\/\/multimedia.cx\/eggs"},{"label":"VP8","link":"https:\/\/multimedia.cx\/eggs\/category\/vp8\/"},{"label":"Understanding the VP8 Token Tree","link":"https:\/\/multimedia.cx\/eggs\/understanding-the-vp8-token-tree\/"}],"_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}]}}