SubSync – architecture overview

This is second post in this series. See Table of Content.

SubSync is written in Python with custom native module compiled from C++ (named gizmo). During synchronization pipeline similar to this is constructed.

Synchronization pipeline (click to enlarge)

While the majority of blocks are part of the gizmo module, pipeline is constructed from the Python code, in subsync/synchro.py. There are three main parts of the pipeline:

  • subs extractor (yellow blocks),
  • refs extractor (blue blocks),
  • correlator (pink blocks).

Subs and refs in this context means words with timestamps produced from your subtitle file (subs) or video that you are synchronizing with (refs).

Subs and refs extraction is done using FFmpeg library components wrapped as C++ objects. Demux (gizmo/media/demux.cpp) is reading input file and extracting single track. If this is audio track, it is decoded by AudioDec (gizmo/media/audiodec.cpp) and converted to the format suitable for speech recognition engine with Resampler (gizmo/media/resampler.cpp). Speech recognition is done via PocketSphinx library wrapped in SpeechRecognition class (gizmo/media/speechrec.cpp). It produces timestamped words annotated with score (floating point value between 0 and 1). This structure is named Word (gizmo/text/words.h#L8)

Similar Words are produces by SubDec (gizmo/media/subdec.cpp), which is used to decode input subtitles. In this case, score is always set to 1.

SubDec is also outputting subtitles in SSA/ASS format, which is FFmpegs internal format for subtitles. They are collected by SubtitlesCollector (subsync/subtitle.py#L57).

Reference words are translated by the Translator (gizmo/text/translator.cpp). It simply tries to lookup in its dictionary every word that is similar enough (using distance function) to the input word. It outputs corresponding translations from dictionary in form of Words with score reduced according to calculated distance. Translator is used only when the language of subtitles is different than the language of references.

Each extraction job is done in separate thread controlled by Extractor object (gizmo/extractor.cpp). It is native thread (as opposed to Python thread). In example above there are three extracting threads, one for subs and two for refs. Words are pushed to Correlator (gizmo/correlator.cpp) which runs in its own native thread by queue (gizmo/text/wordsqueue.h). Correlator calculates two values: delay and speed change which is applied to subtitles gathered by SubtitleCollector. Correlation algorithm will be described in my next post in this series.

Single instance of Translator is used in several threads. It is safe since its pushWord method has no side effects.

Refs are usually extracted with several Extractor threads, each processing different range of timestamps. In this approach we get words from different locations almost immediately which helps Correlator to produce initial synchronization faster and more accurately. Also performance-wise its usually optimal to run one PocketSphinx instance for physical CPU core.

In case when refs are generated from subtitles as well, refs pipeline looks similar to subs one.

In next post I will discuss correlation algorithm in details.


SubSync – synchronize movie subtitles with audio track

Posts in series:

  1. Introduction (this post)
  2. Architecture overview

I’m not dead, just busy. Sorry for the long break without posts.

And recently I’ve created this little tool. It uses speech recognition to synchronize movie subtitles. Here I would like to write about how it works.

So there is speech recognition library. It is pocketsphinx from Carnegie Mellon University. It’s used to produce list of words with timestamps. It works pretty good, but it is not YouTube generated subtitles good. It works well for cleanly recorded voice, in movies with more complicated audio track it will yield inferior results. Maybe 10% of words generated are correct. But it is good enough for us. How? I will explain it in further posts.

There is also option to synchronize with another subtitles. Words generated in this mode will obviously be much better.

Input subtitles that are synchronized are processed similarly, producing timestamped words. If they are of different language, it will be translated using simple dictionary lookup.

Next step is to feed this two lists of words to the correlator. It will pair similar words from both lists, generating pairs of timestamps. It could be visualised as two dimensional chart with two time scales on its axis. It will search for a straight line crossing as many points as possible (+/- epsilon). Finally, equation of that line is used to fix subtitles.

This approach will synchronize subtitles that are delayed and/or with different time rate (useful for frame-based subtitles with mismatched FPS). Obviously it won’t work with anything that has different parts inserted or removed, e.g. synchronizing video with ads and subtitles without it. But still it covers many use cases.

In subsequent posts I will try to explain some implementation details.

Grip updated and ported to Windows

Recently I was working on my indexed grep. Now it could be used with Boost library, as alternative to POSIX. There are build for Windows in the release page. This version could have issues when grepping file with lines longer than 16 kB due to my simplified implementation of getline. I will probably replace it with Boost code, eventually.

There is also significant performance improvement of index generation (gripgen). Now reading file names is not blocking indexer. Also memory organisation was changed to play nicer with cache. As a result indexing over SSD drive is several times faster. Unfortunately, mechanical drive is usually the bottleneck itself, so it will be not much difference. Lower CPU load maybe. And under Windows indexing is painfully slow due to Windows Defender (at least during my test on Windows 10). It looks like Defender is scanning every file that I am opening for indexing. Excluding binary files might help, I guess.

And since file list is read asynchronously, now I could print pretty percentage progress. Of course gripgen can do it after it reads entire list, thus feeding it with find will not show you percentages until find ends.

I was also cleaning up the code, refactoring build system and adding unit tests. Further changes will be mainly polishing and bug fixing, I think. Or not, if I’ll have some great feature idea. We will see.

grip – indexed grep

I’ve created this useful (I hope) tool https://github.com/sc0ty/grip.

It is grep-like file searcher, but unlike grep, it uses index to speed up the search. We need to generate index database first, and then we could grep super fast. Instruction is on the github site, here I would like to share some notes about implementation details and performance.

How it works

This project consist of two commands: gripgen and grip. First one is used to create index database for provided file list (e.g. using external tool like find), second one search for pattern in this database.

Database is based on trigram model (Google is also using this in some projects). Basically it stores every 3-character sequences that appear in the file matched with its path. E.g. world turtle consist of trigrams: tur, urt, rtl and tle. Index format is optimised to fast lookup every file that contains given trigram. To find given pattern, grip will generate every trigram that is part of this pattern and try to find files containing every one of them. It is worth noting that this technique would generate certain amount of false positives. Index database does not contain information about order of trigrams in file, thus grip must read selected files to confirm match. This step could be disabled with the –list switch.

Because gripgen need to be supplied with file list to process, I am using find to prepare such list on the fly. Gripgen is unable to scan files itself by design. This decision vastly simplified its code base, and the many configurable switches of find results in great flexibility of these two tools combined.

Performance

I’ve tested it on Intel Core i5 3470 machine with 5400 RPM HDD, scanning Android code base (precisely CyanogenMod for Motorola XT897).

sc0ty@ubuntu:~/projects/cyanogen-xt897$ find -type f | gripgen
done
 - files: indexed 537489 (5.7 GB), skipped 259992, total 797481
 - speed: 186.8 files/sec, 2.0 MB/sec
 - time: 2877.185 sec
 - database: 493.8 MB in 8 chunks (merged to 1)

It is worth noting, that CPU load was low during the scan (10 – 20%), performance was limited by the HDD bandwidth.

Next I’ve performed several test searches, measuring its execution time.

1.316 sec:    grip -i 'hello word'
6.531 sec:    grip class
0.357 sec:    grip sctp_sha1_process_a_block
0.555 sec:    grip -i sctp_sha1_process_a_block

As we can see here, command that produce fewer results will execute faster (sctp_sha1_process_a_block vs class). It is expected – fewer files must be read. There is also noticeable slowdown in case-insensitive search, as more trigrams is looked up in index (every possible case permutation of pattern).

Next test was performed on laptop with Intel Core i7 L620 (first generation i7) with fast SSD HDD. I’ve scanned several smaller open source projects.

sc0ty@lap:~/projects $find -type f -and -size -4M | gripgen
done
 - files: indexed 52839 (576.1 MB), skipped 11848, total 64687
 - speed: 281.6 files/sec, 3.1 MB/sec
 - time: 187.611 sec
 - database: 62.7 MB in 1 chunk

This time CPU speed was the limiting factor – one core was used at 100% during the scan. I’d like to repeat this test on machine with fast CPU and SSD, but unfortunately I have no access to such device.

In both tests database size was about 10% of indexed files size. This ratio should be proportional to the entropy of indexed files. More entropy means more different trigrams to store. For typical source code tree it is expected to retain this level.

0.444 sec:    grip -i 'hello world'
1.174 sec:    grip class
0.061 sec:    grip extract_lumpname
0.043 sec:    grip -i extract_lumpname

Order of magnitude smaller database with SSD drive results in way faster search. Last case insensitive query was faster than case sensitive probably because files used in previous test was buffered by the system.

Measured times are very promising – instead of wasting long minutes with grep, we could have results in mere seconds (or even in fraction of second), waiting time needed for classic grep only once – for index creation. Of course this approach is not immediately applicable to every situation, but I hope to provide useful tool for its job.

Fixing Audiotrak Maya U5 firmware

TL/DR: I’ve fixed Maya’s firmware to work better under Linux: Audiotrak-Maya-U5-firmware-mod.zip

Part 1: whats broken

Maya U5 is an USB sound card with 5.1 channels support. It has pretty decent sound quality to price ratio. I bought one to use it with my Windows computer. And under Windows it works great.

Then, one day I tried to use it under Linux. As you probably guessed – it didn’t went well. System recognized this device as stereo card, sound went down randomly, volume control was not always working. Audiotrak supports only Windows and OSX, but since this is standard USB audio device it should run under everything.

So of course I asked Google for help, and found firmware that should work. It was better – system detects proper 5.1 device. But other issues still occur.

My second step was to check official website for newer firmware updates. Well, there is one. Great! Well, actually not that great. My system tells me again that I have only two audio channels. Going back to previous firmware. Except firmware flasher attached with older firmware won’t flash my updated card.

Ok, lets compare this two firmware archives. It looks like only four files is changed: flasher exe and dll, VIAFwUpd.ini and one of the bin files. I bet it is the firmware itself. But lets check the ini first.

[DFU]
Firmware=VT1728_20121101_v0.61_0102_05_Release10_Gyrocom_withQsound.BIN

Yep, our firmware blob. And yes, after I’ve changed it to point to the older firmware bin, I can flash it with the new loader. Great work, we are where we started.

Ok, go back to Linux, lets check what kernel knows about this device

$ lsusb -vd 040d:3401

Bus 001 Device 003: ID 040d:3401 VIA Technologies, Inc. 
Device Descriptor:
  bLength                18
  bDescriptorType         1
  bcdUSB               2.00
  bDeviceClass            0 (Defined at Interface level)
  bDeviceSubClass         0 
  bDeviceProtocol         0 
  bMaxPacketSize0        64
  idVendor           0x040d VIA Technologies, Inc.
  idProduct          0x3401 
  bcdDevice            0.61
  iManufacturer           1 
  iProduct                2 
  iSerial                 0 
  bNumConfigurations      1
  Configuration Descriptor:
    bLength                 9
    bDescriptorType         2
    wTotalLength          574
    bNumInterfaces          4
    bConfigurationValue     1
    iConfiguration          0 
    bmAttributes         0xa0
      (Bus Powered)
      Remote Wakeup
    MaxPower              500mA
    Interface Descriptor:
      bLength                 9
      bDescriptorType         4
      bInterfaceNumber        0
      bAlternateSetting       0
      bNumEndpoints           0
      bInterfaceClass         1 Audio
      bInterfaceSubClass      1 Control Device
      bInterfaceProtocol      0 
      iInterface              0 
      AudioControl Interface Descriptor:
        bLength                10
        bDescriptorType        36
        bDescriptorSubtype      1 (HEADER)
        bcdADC               1.00
        wTotalLength          205
        bInCollection           2
        baInterfaceNr( 0)       1
        baInterfaceNr( 1)       2
		
(...)
		
      AudioControl Interface Descriptor:
        bLength                14
        bDescriptorType        36
        bDescriptorSubtype      4 (MIXER_UNIT)
      Warning: Descriptor too short
        bUnitID                10
        bNrInPins               3
        baSourceID( 0)          1
        baSourceID( 1)          7
        baSourceID( 2)         19
        bNrChannels             6
        wChannelConfig     0x003f
          Left Front (L)
          Right Front (R)
          Center Front (C)
          Low Freqency Enhancement (LFE)
          Left Surround (LS)
          Right Surround (RS)
        iChannelNames           0 
        bmControls         0x00
        bmControls         0x00
        bmControls         0x0a
        iMixer                 36 
		
(...)

There are errors in the USB descriptors. Terrific.
Ok, I found something called Thesycon USB Descriptor Dumper – very handy tool. And it told me interesting things.

Information for device MAYA U5 (VID=0x040D PID=0x3401):

*** ERROR: Descriptor has errors! ***

(...)

Endpoint Descriptor (Audio/MIDI):
------------------------------
0x07	bLength
0x05	bDescriptorType
*** ERROR: Invalid descriptor length 0x07
Hex dump: 
0x07 0x05 0x01 0x09 0x40 0x02 0x01 

(...)
Endpoint Descriptor (Audio/MIDI):
------------------------------
0x07	bLength
0x05	bDescriptorType
*** ERROR: Invalid descriptor length 0x07
Hex dump: 
0x07 0x05 0x01 0x09 0x60 0x03 0x01

Yeah, more errors (this error is repeated 7 times for every Audio/MIDI endpoint).

Since I have never done anything more complex with USB descriptors than looking at lsusb output, at this point I had to read a lot. There is official USB documentation here, there are also more approachable descriptions like this and that. Anyway, after some heavy reading I was able to confirm that some descriptors were broken. Probably the mixer descriptor was the problem. There is some kind of array that should map inputs to outputs, but it is truncated. Truncated MIDI descriptors also could make some trouble, but since I rarely play any MIDI, it is not priority for me.

Ok, lets look inside the device. There is VIA Vinyl™ VT2021 codec and VIA VT1728A CPU. It is hard to find anything about this chip more that it is 8032 MCU. Which is something like 8051 with extra peripherals. But wait, there is something similar. VT1620A looks like older brother of this chip. Maybe it is not full spec PDF, but it is some starting point. And IDA handle 8032 assembly.

Part 2: lets fix it

USB configuration descriptor followed by other descriptors could be found at offset 0x15ec (in firmware image release F). My first attempt was to erase MIDI endpoints. Unfortunately, this bricked the box. Flasher stopped to recognise the device.

After second examination of the board, I found 8-pin IC labelled as 25VF512A. An 512 kbit SPI flash. But how to program it without proper hardware? Well, isn’t my Raspberry PI has SPI interface? After quick googling, I’ve found Flashrom. I’ve soldered 5 wires, connected them with Raspberry and was able to resurrect Maya. Back to square one.

Having working solution to unbrick the device, we could make some more intrusive (and complicated) modifications. Ideally it would be to fix every broken descriptor. To do that, we need more room than we have (some descriptors are truncated). So we need to relocate them. But where?

I dumped whole content of flash with my Raspberry. It has 64 kB, but only about 30 kB is used by the image. Rest of the space is empty. So at the end of data, there is plenty of room.

Next we need to find references to this data. 0x15ec could be found only at offset 0x1902. It is not code, and at this moment I couldn’t figure out how it is used, but since we have working backup plan, we are safe. I’ve copied descriptors at the end of image (offset 0x78a0) updated value at 0x1902 to point to the new location and zeroed descriptors data at original location. After flashing (with Audiotrak flasher) it worked!

After many tries I was able to fix mixer and MIDI endpoints. I’ve removed remote-wakeup attribute from configuration descriptor to prevent system from suspending it. Now it is usable under Linux, but still there are minor glitches. I’ve tried to fix also newest image, but could’t make 5.1 to work, so I’ve stayed with older one.

Here is modified (fixed) firmware with new loader, so it could be flashed even on devices with newer firmware.

Audiotrak-Maya-U5-firmware-mod.zip

Vimview: Vim – gdb integration

Vimview is my new pet project. The goal was to follow source code in vim, when using gdb. I wanted it to be done without heavy vim scripting. So I wrote a single file gdb plugin in Python. It makes vim to follow gdb frame (by opening files and moving cursor to the corresponding lines) while vim and gdb are running in separate terminals.

Vim has the ability to be controlled by RPC, gdb can be scripted in Python. That’s all what we need. Plugin and instruction are on my github.

Enjoy.

Reasonable mouse support in tmux

Yes, we finally got sane, configurable mouse support. In version 2.1 they changed mouse-mode, mouse-select-window/pane etc with single mouse switch. Mouse actions now generates key events that can be mapped as ordinary keys.

In my distro (Ubuntu 14.04) there is version 1.8 of tmux, so we need to get latest from sources:

sudo apt-get build-dep tmux
sudo apt-get clean tmux
wget https://github.com/tmux/tmux/releases/download/2.1/tmux-2.1.tar.gz
tar xzf tmux-2.1.tar.gz
cd tmux-2.1
./configure
make
sudo make install

In manual (man tmux) in paragraph MOUSE SUPPORT we could read that new key events available are named MouseUpX, MouseDownX and MouseDragX where X is button no (1-3), followed by location suffix that describe where you are pointing cursor (Pane, Border or Status). So when you right-click on the status line, events MouseDown3Status and MouseUp3Status will be emitted.

Ok, but how is that better than the former method? You could now define your mouse behaviour as you like. That include (some limited) use of scripting. E.g. to spawn new window after selected by right click on the status line label, you could add something like this to your .tmux.rc:

# don't forget to turn mouse on
set mouse on

bind-key -n MouseDown3Status new-window -a -t=

Option -t= means that the target is window/panel (depends on command) that is clicked.

Or maybe you want to be able to reorder windows in status bar by drag & drop?

bind-key -n MouseDrag1Status swap-window -t=

Ok, that’s great, but we all know what you really want in tmux.

Scroll with mouse in every situation

Yep, it is possible with tmux 2.1. It is not pretty, but it works. And by every situation I mean normal and alternative terminal mode and also tmux copy mode (when you can scroll through history). You could even scroll up to access this mode.

bind-key -n WheelUpPane \
    if-shell -Ft= "#{?pane_in_mode,1,#{mouse_button_flag}}" \
        "send-keys -M" \
        "if-shell -Ft= '#{alternate_on}' \
            'send-keys Up Up Up' \
            'copy-mode'"

bind-key -n WheelDownPane \
    if-shell -Ft= "#{?pane_in_mode,1,#{mouse_button_flag}}" \
        "send-keys -M" \
        "send-keys Down Down Down"

Command if-shell -F is used to check given variable value. If it is non-zero and non empty, first argument will be evaluated, otherwise, second one. Flag pane_in_mode is set if pane is in tmux copy mode. mouse_button_flag is set when running app is actively capturing mouse (like vim). alternate_on is set whenever terminal working in alternate mode (where there is no history to scroll by, like top). If you want to debug these variables, you could print them in status line

set -g status-right 'mouse_btn_flag:#{mouse_button_flag} pane_in_mode:#{pane_in_mode} alt:#{alternate_on}'

Construction like #{?pane_in_mode,1,#{mouse_button_flag}} checks the value of first variable and returns 1 if it is non-zero, second variable value otherwise. It is logical OR constructed with if-shell syntax.

Starting from second example – wheel down. If we are in tmux copy mode or running app want to catch mouse, we send mouse escape strings directly (send-keys -M will pass through mouse events). Otherwise we are sending down arrow key three times. Why not pass mouse event in all cases? Well, if running app don’t tell terminal to catch mouse, most terminals will be doing same thing. That’s why you could scroll through less and man pages.

Wheel up scenario has one more condition added. You can go to copy mode, and then scroll through tmux history when you are not in alternative mode.

This is most sane setup that I’ve been able to come with. It works with shells, vim, man pages, less, htop, mc without breaking terribly anything. One drawback (for me) is, scrolling through tmux copy mode progress by one line at a time. It probably could be fixed by adding extra condition to these lines, but I’m afraid that it will break something. And it is obfuscated enough, already.

For reference, here is my .tmux.conf.

Kernel for NAS ZyXEL NSA310

There are some kernels for this NAS on the web (binaries and configs), but everything I could find was super old (like kernel 3.6.9 old). Because I’ve been able to successfully build current longterm version of Linus tree kernel, here is me sharing my solution.

It is based on this instruction. The kirkwood_defconfig was merged with mvebu_v5_defconfig so we are using the second one instead. I’ve pushed my config, patches and cross-compilation script to my github: https://github.com/sc0ty/nsa310-kernel. There is everything explained in README.md, I won’t repeat myself here. I’ll try to keep this repository up to date with Linus kernel as long as I am using this NAS myself.

And here are binaries (uImage with modules):

f.lux hotkeys modification

I’ve started using f.lux some time ago and now I cannot live without it. But there is one disadvantage considering my use case. Whenever I want to see a movie (which is usually at evening when f.lux is making everything reddish) I have to disable it manually. Through context menu. Because hotkey allows you to disable it only for one hour. And my movies usually are longer than that. So what can I do? Fire an IDA, of course.

f.lux debugging #1

Where to start? I’ve tried to find string that is shown after pressing these keys (ALT + END): “for an hour” and “f.lux is back”. Strings window found it at address 0x483850 and 0x483860 (f.lux v. 3.10 for Windows). IDA could find only one reference to these addresses in single function sub_458330. Great, lets put breakpoint at the beginning of this function and lets see what happen.

Breakpoint will hit frequently after the program starts. It must be some kind of message processor. Ok, lets put breakpoints on lines referenced to strings (0x4585D6 and 0x4585E2 – see picture on the left) instead of begginig of function. Now we can see that it hits only on hotkeys, but not on menu click. Great.

Looking around this place we could find an interesting value. At address 0x4585B9 there is label pointing to double float:

.rdata:00490240 dbl_490240 dq 3600.0

3600 which is number of seconds in hour. Coincidence? And what is this strange fld instruction? Probably some mov with float argument. Lets find it.

f.lux debugging #2

I’m not sure but it looks like this value is placed on the stack as argument to sub_452BD0 function. Lets break on this function and try to modify the value on the stack. I found online float to binary converter here http://babbage.cs.qc.cuny.edu/IEEE-754.old/Decimal.html. I’ve tried to change this to 10 secs, which is 0x4024000000000000 (use double precision). It works, so all we need to do is to patch executable with value corresponding to 3 hour time or so and maybe change strings accordingly, right?

Why not “disable until sunrise”?

Why not just remap ALT + END to call this function? It has no shortcut whatsoever. Lets find this string. It is used at address 0x457DD0 as parameter to AppendMenuA function. But it is here registered, not executed. Maybe we should try different approach: lets find xrefs to sub_452BD0. We should find proper message processor associated with menu this way.

There is five of them. Lets break on four yet unexamined. This way we will detect the one called by menu. As we can see, it is 0x457FCF. But wait, there is similar code next to it.

f.lux debugging #3

Only difference is in timeout parameter passed to our function – it is -1 this time. Is it some special value to indicate this “until sunrise” mode? Lets find out. We already have breakpoint in here, so we only have to click this option from menu. And it breaks!

Finally our hack comes to modify this single value at address 0x4585B9 (hotkey handling function). Or I suggest to modify instruction to load value -1 from address 0x4901F8 instead to not affect other places where this value is used (and there is several such places). And maybe changing string “for an hour”.

Oh wait, “until sunrise” is too long to fit in there! What now?

Don’t worry, there are at least two possible solutions. We could use another string here. “Until sunrise” is presented at 0x483888. And if you want string that starts with lower case, you could use “Disable until sunrise” at 0x483724 but skipping the first word.

If you still couldn’t find any useful string, you could always add new one. At the end of .rdata section there is more than 400 bytes unused. You can put your string there. Don’t forget to update virtual size of this section in section header.

f.lux debugging

Unfortunately f.lux license forbids me to publish modified version. Instead, I would present patching instruction in form that it would be easy to patch with any hex editor.

Format:
address: original value -> new value
where address is file offset hexadecimal value.
"Until sunrise" patch:
579BB: 40 02 49 00 -> F8 01 49 00
579D7: 60 38 48 00 -> 2C 37 48 00
"3 hour" patch:
8F640: 00 00 00 00 00 20 AC 40 -> 00 00 00 00 00 18 C5 40
82C60: "for an hour" -> "for 3 hours"