Showing posts with label code. Show all posts
Showing posts with label code. Show all posts

2011-04-09

What happens if...

Back again. This time I fished out something I had put apart for future fun. It is simply a piece of code that, like a lot of pieces of code I've seen recently, drove me crazy; since it is clearly wrong, but people using it think it is right, just because it happens that it works. (Moreover names chosen for the functions are misleading, but this is a different fact).

How about that, you ask: if something happens to work, it means it is right. Doesn't it? Wrong. Of course, it does not work miraculously: it works since the "real world space" of inputs which feeds it, is smaller than the "theoretical space" of inputs that the code pretends to handle.

Less words, let's look at the code (pseudocode).


procedure Copychar (start, end : integer,
src, out dest, repl : string);

var tmp : string,
i, k : integer;

k := 0;
for i := 0 to src.length;
if i >= start-1 and i < repl.length then
tmp[k] := src[i];
k := k + 1;
else if i >= end then
tmp[k] := src[i-1];
k := k + 1;
end if;
end for;
dest := tmp;
end procedure.


Hopefully every real programmer (being using Pascal or whatever) can see how ill this code is (and the procedure name does not explain what the code's intentions were). First, the for runs from the first character (indexed by 0) to past the last one (indexed by the length of the string minus 1); the guard ring is on the length of the repl string, not on src that is the variable indexed by i. If the repl string is longer than src, bad things may happen.

So the procedure must have at least this constraint: repl.length <= src.length; with this (undeclared) constraint, the index i can index src correctly in the first if. When the index has passed that "threshold" the else if is taken into account for sure, and its body executed when i >= end.

This code is so evil that it is hard to explain why (and it is hard to imagine that it did the job it was written for! But if I would show the rest of the code, you will see that this is very specialized code, camouflaged as generic function, used in a very "special" way, in a very "special" context).

The intention of the procedure (by the name and by input parameters) seemed to be to substitute a string with another, where of the old string we know just where it starts, and where it ends. But if we take a look at it, we see it does not read from repl, and it does indexing in the wrong way...

A correct, correctly general procedure could be instead (I am using more abstractness in place of explicit for loops):


procedure ReplaceStrPart (start, end : integer,
src, out dest, repl : string);

dest := "";
dest := dest + src[0:start-1];
dest := dest + repl;
dest := dest + src[end:];

end procedure.


Hopefully everyone who can be considered a programmer can translate this with for loops and indexes, if the language does not support strings slicing or similar syntax (note: in the syntax a[i:f], if i > f, nothing is copied, while a[i:i] is the same as a[i] and picks the i-th character).

This procedure does what we expect and has a name that is a little bit better.

As for the original evil code, the programmer failed to write a senseful generic function/procedure; rather, he proceeded in a trial-error-fix fashion, in a "limited input space", and he had to "compensate" for what likely he recognized as odd behaviour, until he reached the purpose... I would say, by chance. And everything went fine since the "input space" stood limited, though (I know this) there was no reason why it should happen, there was no a special constraint or handshake about that... it simply was so since people have their habits and generated strings keep their "places"...

2010-12-08

How many days in a month?

A coworker proposed to me a little challenge sometimes I think about. My first solution, though correct, was rejected since it used the ternary operator ?: and there's a way to succeed without.

Today is holiday here in Italy and I am using my spare time pushing the button of my almost-dead laptop just to hear the one-long-beep-two-short-beeps sequence (hoping not to hear it), then hold the button to turn it off and then stick hitting keys on the job laptop — where I am now.

After I've read a lot of pages from On the Edge - The Spectacular Rise and Fall of Commodore, almost finishing it, I decided to let my eyes be enlightened by the LCD of the job laptop, where there's nothing more interesting to do than surfing the net and using gcc (MinGW) in the unpleasant environment MS Windows XP provides.

Ok stop making the post longer than it could be...

The challenge was: using just an expression, get the number of days in a specified month (given as a number from 1 to 12). No-one told me about constraints for February so I assumed it has 28 days; moreover, initially there was no prohibition of the ternary operator...

My first solution was:

g = 31 - ((m < 9)? (m+1)%2 : m%2) - 2*(m==2);

which worked on all the system I've tested it (MS Windows, Sun Solaris on SPARC, and GNU/Linux on Intel) but obviously contains a possible bug dued to m==2 that does not need to be evaluated as 1 when true, though likely it does (As std C says, boolean expressions evaluate to 1 when true; unless we're dealing with non std compliant compiler, or if we translate the idea in other languages).

My second solution is:

g = "103012310321"[m-1] - 18 - (m&2);

This one is maybe tricky but is more robust (provided m is in [1,12] and we are on a system using ASCII), and can be easily modified in order to yield 29 for February. Moreover, what it makes me like it is that it uses something rarely many non-expert programmers are aware of about C (I mean using "array notation" for a literal string). The practice could be marked as bad, but it is great when codegolfing!

About codegolfing... If I am not wrong, that code in GolfRun would be "103012310321"m(=18-m2&- but currently I can't test it since my already-compiled (for GNU/Linux) work-in-progress GolfRun interpreter is on the Real Out-Of-Work Laptop, though I could checkout the SVN repository on this machine and try to compile it with MinGW on MS Windows — what a pity it uses Gtk+ and GMP extensively and I want not to go into the trouble of having them properly installed (ready for development usage) on this hateable system.

The third solution to the challenge that comes into my mind is about looking at the bits. The previous solution already does it... a bit! But the idea can be extended; for this purpose I've made the following table


XY ABCD
31 1F 1 11 11 1 0001
28 1C 1 11 00 2 0010
31 1F 1 11 11 3 0011
30 1E 1 11 10 4 0100
31 1F 1 11 11 5 0101
30 1E 1 11 10 6 0110
31 1F 1 11 11 7 0111
31 1F 1 11 11 8 1000
30 1E 1 11 10 9 1001
31 1F 1 11 11 10 1010
30 1E 1 11 10 11 1011
31 1F 1 11 11 12 1100


We have four bits in input and we need to "produce" just 4 "patterns" (two bits) in output. The boolean table old school (and semplification thereafter) will give us a solution (paper and pen here for a while...) (^ stands for an overbar on the following letter, i.e. for the logical not):


^X = A + B + ^C + D
^Y = ^A^D(B + C) + AD^B



That gave me the code:


g = 28 |
((((((((~m)>>2)&((~m)<<1)&((~m)>>1))^1) &
(((~m)^2)&((~m)>>3))) |
((m>>3)&((~m)>>2)&m&1))^3)&3);


I am rather dissatisfied with this: surely it can be optimised someway, e.g. by doing simple observations like: no need to handle higher bit in logic since it needs just an exception (when m is 2); try to work in "positive logic"; mix ideas from the previous solution with the "gate logic" stuff... Anyway, for now it is enough, I have to go and do better things: I have a button I must push.

2010-05-24

The YT case (part one)

It is a problem that goes and returns back periodically: how can I download YouTube videos? It's not a problem that has a forever solution since YouTube changes things. Maybe it does so also to make it harder to download videos: we must "pass" through them, so they can control contents better (DRM!) and earn through traffic and data we produce using their service... Even supposing we're on the dark side of believing their shameless lies (rather than on the bright side of thinking they are just taming us turning our bodies in batteries that produce electro-money only for them), we could wish to download a video the author released after some permissive license.

Searching for already-made mass solutions we are just caught in the ads-worlds. So we seek a little bit differently, not too much, and we find interesting sites giving real solutions. I've started my alone researches but dropped them since I've found these working solutions (this is one of the cases you're happy to find people smarter and more efficient than you). Nonetheless I will write some of my researches here, they could be of interest for someone now or in the future.

But first let's see working solutions I've tried (my video target was always the same but I've no reasons why to think they should not work with other videos). Not everybody is able to use these solution and because of this I am working on a C# porting of one of these. Hope I will finish it (I am not a C# programmer, but it's time I start to taste it a bit...)


  • GAWK solution. This was the second found code I've tried and the first to work. Unluckly perl scripts (one-liners) by the same author (see his other post) failed. I suspect it could be only because of the User-Agent, but I've not done tests yet. If it would be so, there's an easy fix.

  • Youtube-dl.py; this one looks cool, it seems to support several sites (despite its name), it looks well-written, and the -g option can be specified if one wants to use his/her custom downloader: I've tried wget (without spoofing) and worked!



And now, the part no-one is interested in: my researches. Read at your own risk (if you can waste your time I suggest studying the code of the gawk or python solutions, rather than reading what follows). If you want to read it, consider it as a muddle of scattered thoughts; possible audience maybe should be a little bit computer literate.

Discontinued analysis/study of the YT case


Request URL is simply /watch?v=ID where ID is a video_id identifying the video. This brings us to /v/ID, through the browser it sends back a compressed swf file. Disassembling the file with flasm we see defining a set of variables; one seems to hold the URL of the skin of the player (another swf file at http://s.ytimg.com/yt/swf/cps-vfl165272.swf at least in this case); video_id set to the same value of ID; a variable sk holds a key, it changes every time I download the file. They may appear other variables "mirroring" URL "parameters". Searching it seems like the work this swf file does was indeed done by a simple html file in ancient ages...

At some point this swf contains code that seems to construct a URL, so I followed it a bit and wrote the following pieces. Not so interesting after all :( A a little bit more readable form of the flasm-flavoured flash disassembled code is

main = function ('clip') ( ... )
{
loadClip = createEmptyMovieClip ...........
r:2 = new MovieClipLoader .................
clip.addCallback .......

. (nothing interesting here...)
.
.

r:3 = clip.swf
i.e. "http://s.ytimg.com/yt/swf/cps-vfl165272.swf"
1 2 3 4
0123456789012345678901234567890123456789012

r:4 = clip.swf.split("/")[2]
gets the domain ("s.ytimg.com")

r:4 == "s.ytimg.com"
branchIfTrue label5

i.e. is the domain s.ytimg.com? Yes, in this case, so
branch

.
. (see CASE B code)
.
label5:
loadClip.loadClip(r:3, r:2)

where r:3 is clip.swf, see above
and r:2 is an instance of MovieClipLoader

}


In case the domain is not s.ytimg.com, it builds an URL; this is not the case but it could be interesting.

* CASE B *

r:5 = clip.swf.indexOf("-vfl")
r:5 is 29 in my case
r:6 = clip.swf.indexOf(".swf")
r:6 is 39 in my case
r:7 = clip.swf.indexOf("/swf/") + 5
r:7 is 21 + 5 (index pointing to cps- or whatever
comes after /swf/ part

r:8 = "cps"
if not (r:5 > -1) then
// -vfl not found in the string clip.swf
r:8 = clip.swf.substring(r:7, r:6)
i.e. everything after /swf/, less the three letters ext
end if

r:9 = loadClip._url.split("/")[2]
r:3 = "http://" + r:9 + "/swf/" + r:8 + ".swf"
i.e. builds
http://domain of _url/swf/thing.swf


The interesting part seems to be when the domain is not s.ytimg.com. But it appears the _url variable of clip, which is not set nowhere here... in this case at least. The domain matchs so no need to have _url set, but I wonder when it does not match. I suspect indeed this one is the wrong swf to look for. Maybe URL parameters may change things and this very same code serves other "purposes" too. Interesting to note that this flash says

System.security.allowDomain("*")


So theoretially this swf is usable also externally; this is obvious thinking about embedding. The set of variables the code assigns is:

// the "cover" of the video
iurl = 'http://i4.ytimg.com/vi/ID/hqdefault.jpg'
el = 'embedded' // embedded where? in the default flash player?
fs = '1' // full screen
title = '...'
avg_rating = '4.7547...' // wow how many digits for the rating!
video_id = 'ID'
length_seconds = '..' // number for its length
allow_embed = '1' // interesting...
swf = 'http://s.ytimg.com/yt/swf/cps-vfl165272.swf'
// Security Key? ?
sk = 'TK755pvEYU-oGqmzRTwz7fq1dipYreRnC' // or alike
rel = '1'
cr = 'US'
eurl = ''


I am wondering what happens if allow_embed is 0 and I modify it into 1 and use this as "embedding" trampoline.

In the html page of the video (the one we get with /watch?v=ID there are alternate addresses, serving informations in JSON+OMBED or XML+OEMBED, oembed, flying around these we can find an address to use with the RTS Protocol, tried this road, mplayer understand the protocol, but it seems the Google RTSP Server does not like too much it and stop the connection. (SDP used too).

Once upon a time it existed a so called get_video API, it seems to work still but it is different the way we can get the needed parameters (see youtube-dl.py with -g option), which are different too. In the URL given by youtube-dl.py appear video_id (which is ID), t (token... could it be sk? They are not the same, it seems), eurl (null...), el (detailpage), ps (default), gl (US), hl (en); some appears in the analysed swf too. But the most important is for sure the token (t).

Discontinued. Youtube-dl.py works, I'll look how it acts and write something runnable on Windows machine by people not interested in installing python on their system (bad very bad).