Sorry for late reply. I have analysed regression tests. It seems OpenBSD's
sdiff works correctly and GNU sdiff breaks own rules:
http://www.gnu.org/software/diffutils/manual/html_node/Side-by-Side.html
http://www.gnu.org/software/diffutils/manual/html_node/Side-by-Side-Format.html
For example, GNU sdiff manual writes:
       -w NUM  --width=NUM
              Output at most NUM (default 130) columns per line.
But unfortunately, with long lines, instead of 130 it could take only 126
columns. Also, as gutter between two columns it could take a ( instead of
whitespace.
But I don't think it could be a serious compatibility problem, which wouldn't
let use to replace sdiff.

If nobody will hoist objection flag - I will import it.

-- 
Best regards,
Mindaugas