Recherche avancée

Sur d’autres sites (4473)

• Understanding the VP8 Token Tree

  7 juin 2010, par Multimedia Mike — VP8

  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 David Conrad’s comment on my last post regarding my difficulty understanding the VP8 spec 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.

  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 :

  PLAIN TEXT

  C :

  1. const tree_index coef_tree [2 * (num_dct_tokens - 1)] =
  2. {
  3.  -dct_eob, 2,        /* eob = "0"  */
  4.   -DCT_0, 4,        /* 0  = "10" */
  5.   -DCT_1, 6,        /* 1  = "110" */
  6.    8, 12,
  7.    -DCT_2, 10,      /* 2  = "11100" */
  8.     -DCT_3, -DCT_4,    /* 3  = "111010", 4 = "111011" */
  9.    14, 16,
  10.     -dct_cat1, -dct_cat2, /* cat1 = "111100", cat2 = "111101" */
  11.    18, 20,
  12.     -dct_cat3, -dct_cat4, /* cat3 = "1111100", cat4 = "1111101" */
  13.     -dct_cat5, -dct_cat6 /* cat4 = "1111110", cat4 = "1111111" */
  14. } ;

  Here is what the table looks like when you make a tree out of it (click for full size image) :

  
  
  

  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, "decoding of certain DCT coefficients may skip the first branch, whose preceding coefficient is a DCT_0." I confess, I didn’t understand what "skip the first branch" meant until I drew the tree.

  
  
  

  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 n points to elements n*2 and n*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.

• A *hot* Piwik Community Meetup 2015 !

  10 août 2015 — Community

  Last weekend I arrived in Germany to attend the Piwik Community Meetup 2015 and now I am in Poland. I joined Piwik PRO back in May as enterprise support project coordinator in North America. I am now writing this from the Piwik PRO main office in Wrocław, where I’ll be working from for the next two weeks.

  The meetup was HOT in every sense ! Berlin temperatures reached 35 degrees (celsius), as I finally meet in person several long-time, dedicated Piwik community contributors.

  

  Meetup preparation in Berlin, photo by M. Zawadziński, licensed under CC-BY-SA 4.0

  Pictures from the meetup preparation sessions
  

  In the first leg of my trip I was in Berlin to meet Piwik community members and Piwik PRO staff to prepare for the 2015 annual Piwik community meetup. These are my notes taken during the meeting at the request of one of my colleagues. I also relayed live on Framasphère, Twitter and IRC.

  

  Community discussion at the meetup, photo by D.Czajka, licensed under CC-BY-SA 4.0

  More pictures from the Piwik meetup
  

  This was harder than I expected, as I took notes with my laptop, pictures with my phone, wrote live to social media (using the Android Diaspora Native Web App), and used my laptop to relay on IRC. Going forward this requires better preparation, I was glad I had a few links and pictures ready before hand but it really requires intense focus to achieve this. I am glad presenters were patient when I requested repeating some of the ideas they shared. I am also a bit disappointed not much happened in IRC.

  Two day preparation sessions

  The discussions and session we had during the two days prior to the meetup are available here.

  We gathered in rented apartments in Berlin, this reminded me very much of similar community gatherings and perhaps of BarCamp and, at a much smaller scale, UDS sessions.

  

  Piwik Pizza !, photo by F. Rodríguez, licensed under CC-BY-SA 4.0

  A list of ideas of topics was initially submitted, we then proceeded to have scheduled sessions for open discussion. Several people shared their concern there was no possible remote participation which led to making public the Trello boards used/linked here.

  Note : The Trello links below still have action items and notes that are pending bug report / feature requests filing which should happen over the coming weeks. Most importantly, many action items will need identifying leads for different community team including Translations and Documentation, and better coordination of coming community engagement.

  Monday sessions consisted of the following subjects :

  • What are Piwik values & how to communicate them ? (see below for details)
  • How to encourage and recognize new external contributors ?
  • How could we double the Piwik userbase ?
  • How Community can organise help resources

  On Tuesday we met again to discuss the following subjects :

  • Piwik Long Term support (LTS)
  • How do Piwik.org (project) and Piwik PRO (company) sit together / are organized ? – An important part of this session was about having better communication channels and improving the new team page (bug #8520 and bug #8519, respectively)
  • Improving usability of Piwik e.g. for new users – this last session was not held has we ran out of time and prepared to go to the meetup venue.

  Some more details about individual preparation sessions

  What are Piwik values & how to communicate them ?

  The main subjects in this session were important changes proposed in the project mission and values. This was edited directly on on the wiki page on GitHub, some of the changes can be seen by comparing revisions.

  Piwik mission statement (bug #7376)

  “To create the leading Free and open source analytics platform, and to support global organisations and communities to keep full control over their data.”

  Our values

  • Openness
  • Freedom
  • Transparency
  • Data ownership
  • Privacy
  • Kaizen (改善) : continuous improvement

  This was also presented by Matthieu Aubry at the meetup and is published in the Roadmap page. Bringing more visibility and perhaps having a top page for Mission and Values was also brought up.

  Meetup agenda and notes

  The official agenda is available here.

  Many Piwik PRO employees stayed in Berlin for the meetup, and we had good participation although less than last year in Munich as my colleagues told me. Some were consultants, others staff from public organizations, universities, etc. In retrospect considering the very hot weather and summer holidays the attendance was good. I was very happy to arrive at the beautiful Kulturbrauerei and enter the air-conditioned Soda Club. T-Shirts were waiting for all attendees and free drinks (non-alcohol !) were welcome

• Further Dreamcast Hacking

  3 février 2011, par Multimedia Mike — Sega Dreamcast

  I’m still haunted by Sega Dreamcast programming, specifically the fact that I used to be able to execute custom programs on the thing (roughly 8-10 years ago) and now I cannot. I’m going to compose a post to describe my current adventures on this front. There are 3 approaches I have been using : Raw, Kallistios, and the almighty Linux.

  
  

  Raw
  What I refer to as "raw" is an assortment of programs that lived in a small number of source files (sometimes just one ASM file) and could be compiled with the most basic SH-4 toolchain. The advantage here is that there aren’t many moving parts and not many things that can possibly go wrong, so it provides a good functional baseline.

  One of the original Dreamcast hackers was Marcus Comstedt, who still has his original DC material hosted at the reasonably easy-to-remember URL mc.pp.se/dc. I can get some of these simple demos to work, but not others.

  I also successfully assembled and ran a pair of 256-byte (!!) demos from this old DC scene page.

  KallistiOS
  KallistiOS (or just KOS) was a real-time OS developed for the DC and was popular among the DC homebrew community. All the programming I did back in the day was based around KOS. Now I can’t get any of it to work. More specifically, KOS can’t seem to make it past a certain point in its system initialization.

  The Linux Option
  I was never that excited about running Linux on my Dreamcast. For some hackers, running Linux on a given piece of consumer electronics is the highest attainable goal. Back in the day, I looked at it from a much more pragmatic perspective— I didn’t see much use in running Linux on the DC, not as much as running KOS which was developed to be a much more appropriate fit.

  However, I was able to burn a CD-R of an old binary image of Linux 2.4.5 compiled for the Dreamcast and boot it some months ago. So I at least have a feeling that this should work. I have never cross-compiled a kernel of my own (though I have compiled many, many x86 kernels in my time, so I’m not a total n00b in this regard). I figured this might be a good time to start.

  The first item that worries me is getting a functional cross-compiling toolchain. Fortunately, a little digging in the Linux kernel documentation pointed me in the direction of a bunch of ready-made toolchains hosted at kernel.org. So I grabbed one of the SH toolchains (gcc-4.3.3-nolibc) and got rolling.

  I’m well familiar with the cycle of 'make menuconfig' in order to pick configuration options, and then 'make' to build a kernel (or usually 'make zImage' or 'make bzImage' to create compressed images). For cross compiling, the primary difference seems to be editing the root Makefile in the Linux source code tree (I’m using 2.6.37, the latest stable as of this writing) and setting a value for the CROSS_COMPILE variable. Then, run 'make menuconfig' followed by 'make' as normal.

  The Linux 2.6 series is supposed to support a range of Renesas (formerly Hitachi) SH processors and board configurations. This includes reasonable defaults for the Sega Dreamcast hardware. I got it all compiling except for a series of .S files. Linus Torvalds once helped me debug a program I work on so I thought I’d see if there was something I could help debug here.

  The first issue was with ASM statements of a form similar to :

  mov #0xffffffe0, r1
  

  Now, the DC’s SH-4 is a RISC CPU. A lot of RISC architectures adopt a fixed instruction size of 32 bits. You can’t encode an entire 32-bit immediate value inside of a 32-bit instruction (there would be no room for the instruction encoding). Further, the SH series encoded instructions with a mere 16 bits. The move immediate data instruction only allows for an 8-bit, sign-extended value.

  I decided that the above statement is equivalent to :

  mov #-32, r1
  

  I’ll give this statement the benefit of the doubt that it used to work with the gcc toolchain somewhere along the line. I assume that the assembler is supposed to know enough to substitute the first form with the second.

  The next problem is that an ’sti’ instruction shows up in a number of spots. Using Intel x86 conventions, this is a "set interrupt flag" instruction (I remember that the 6502 CPU had the same instruction mnemonic, though its interrupt flag’s operation was opposite that of the x86). The SH-4 reference manual lists no ’sti’ instruction. When it gets to these lines, the assembler complains about immediate move instructions with too large data, like the instructions above. I’m guessing they must be macro’d to something else but I failed to find where. I commented out those lines for the time being. Probably not that smart, but I want to keep this moving for now.

  So I got the code to compile into a kernel file called ’vmlinux’. I’ve seen this file many times before but never thought about how to get it to run directly. The process has usually been to compress it and send it over to lilo or grub for loading, as that is the job of the bootloader. I have never even wondered what format the vmlinux file takes until now. It seems that ’vmlinux’ is just a plain old ELF file :

  $ file vmlinux
  vmlinux : ELF 32-bit LSB executable, Renesas SH,
  version 1 (SYSV), statically linked, not stripped
  

  The ’dc-tool’ program that uploads executables to the waiting bootloader on the Dreamcast is perfectly cool accepting ELF files (and S-record files, and raw binary files). After a very lengthy upload process, execution fails (resets the system).

  For the sake of comparison, I dusted off that Linux 2.4.5 bootable Dreamcast CD-ROM and directly uploaded the vmlinux file from that disc. That works just fine (until it’s time to go to the next loading phase, i.e., finding a filesystem). Possible issues here could include the commented ’sti’ instructions (could be that they aren’t just decoration). I’m also trying to understand the memory organization— perhaps the bootloader wants the ELF to be based at a different address. Or maybe the kernel and the bootloader don’t like each other in the first place— in this case, I need to study the bootable Linux CD-ROM to see how it’s done.

  Optimism
  Even though I’m meeting with rather marginal success, this is tremendously educational. I greatly enjoy these exercises if only for the deeper understanding they bring for the lowest-level system details.