Monday, July 24, 2023

I am such a rust programmer.

 I tried to see how to use `static mut SOMEVAL` - turns out, I can do it by wrapping them in `unsafe`. I somehow feel guilty of doing this.



use std::thread;

static mut SOMEVAL: i32 = 10;
const THREAD_COUNT: usize = 100;

fn main() {
    let mut handles = vec![];
    for _i in 0..THREAD_COUNT {
        handles.push(thread::spawn(move || {
            unsafe {
                SOMEVAL += 1;
            }
            // panic!("hehe");
            1
        }));
    }

    for handle in handles {
        // ignoring return value with ok(), 
        // which might not always work nice.
        // See https://users.rust-lang.org/t/what-is-the-best-way-to-ignore-a-result/55187/6
        if handle.join().ok().unwrap() == 0 {
            println!("Well, that's awkward");
        }
    }

    unsafe {
        println!("sum total {}",SOMEVAL);
    }
}

Saturday, September 6, 2014

String matching with *, what is the complexity?

Imagine you have a long input string and a "regexp" in the following form abc*efg*etc*. Which means that you are looking for a string that starts with abc, followed by some number of whatever characters, followed by efg, followed by...
So, here is a claim: to answer whether the string matches the "regexp", the complexity is linear for the size of the string you are looking into + the size of the regexp.
Why?
We will use KMP string matching algorithm with O(n+m) complexity, but we will use a detail of implementation of algorithm: when it finds a string, it has not looked at more than offset to string + size of string characters out of n.

So how does our algorithm work?
- if we see a set of characters in the beginning of regexp, see whether regexp starts the same way as string till the *. from now on:
- if we see a set of characters in regexp, look for that.
- if we see a star, ignore that.
- when we arrive at the end of regexp, see whether the end of search string has been achieved as well (if * is end of regexp, then yes, otherwise look at offsets in search string).
- if any of the above things does not work, return failure.

What is the complexity? Whenever we search inside the string, we use KMP and it works in O(n+mi), where mi is the size of current set of characters we are looking for. Sum of all mi's is ~m - the length of regexp. If we have many mi's why isn't the complexity O(n*count mi's + m)? The reason is that when KMP finds a string, it stops. So, if a string is found, we have looked at all characters that where before the string + the string, but not more. In our algorithm it means that we never go through the string again! Or, in other words: in KMP subroutine we don't look at the same characters in two subsequent calls. So, the overall complexity - O(n+m). What if KMP fails? Well, then we don't call another KMP.

Here is KMP: http://www.ics.uci.edu/~eppstein/161/960227.html


Saturday, August 9, 2014

How to call native code from node.js?

Looks like two options are available: use node-ffi, which supports loading a native dynamic link library and then calling things in cdecl (guess). The other is writing your own module, described here: http://syskall.com/how-to-write-your-own-native-nodejs-extension/index.html/

Node-ffi is here: https://github.com/node-ffi/node-ffi. Let's create a dll for it:
In Visual studio new c++ project, dll type. Then:
#include "stdafx.h"
#include <iostream>

extern "C"
__declspec(dllexport)  void stdoutput()
{
std::cout << "test output";
}

extern "C"
__declspec(dllexport)  void crash()
{
__asm
{
int 3;
}
}

End result:
C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\bin\dumpbin.exe c:\users\ledin_000\documents\visual studio 2013\Projects\sample_dll\Debug\sample_dll.dll
"C:\Program Files (x86)\Microsoft Visual Studio 12.0\VC\bin\dumpbin.exe" /exports "c:\users\ledin_000\documents\visual studio 2013\Projects\sample_dll\Debug\sample_dll.dll"
...
    ordinal hint RVA      name

          1    0 0001101E crash = @ILT+25(_crash)
          2    1 000110DC stdoutput = @ILT+215(_stdoutput)

npm install node-ffi suggested to install module ffi.
At some point npm errorred out because I did not have C:\Users\<username>\AppData\Roaming\npm directory.
After that, compiles stuff using my visual studio. Interesting security consequences. So I have trust npm. It does do ssl connection to the servers where it downloads things from. Fiddler says.
Turns out my node installation is 64 bit. Kind of expected. So now: ::DebugBreak(); instead of the __asm sequence. 
var ffi = require('ffi');

var funcs = ffi.Library('sample_dll.dll', {
  'stdoutput': [ 'void', [  ] ],
  'crash': [ 'void', [ ] ],
});

funcs.stdoutput();
funcs.crash()

Didn't crash. Why not?
I guess I need to execute it under debugger.
I will sleep for 20 seconds, to enable attach with visual studio. 
JS does not have a sync sleep function, so npm install sleep. 
Node populates C:\Program Files\nodejs\node_modules\sleep, so it is easy to look how a module looks like. 
Somehow I cannot see a nice callstack when attaching and waiting for Debugbreak(). Debugbreak happens, but not with expected callstack.
So I do:
windbg node exp2.js
sxe ld sample_dll -- wait till loading of sample_dll happens.
x sample_dll!*crash* -- to see I have symbols, which I have in path.
then
bu sample_dll!crash
and...
0:000> k
Child-SP          RetAddr           Call Site
00000000`0035f4c8 00007ffe`15ff9dc3 sample_dll!crash [c:\users\<user>\documents\visual studio 2013\projects\sample_dll\sample_dll\sample_dll.cpp @ 15]
00000000`0035f4d0 00007ffe`15ff39b6 ffi_bindings!ffi_call_win64+0x77
00000000`0035f510 00007ffe`15ff26df ffi_bindings!ffi_call+0xa6 [c:\node_modules\ffi\deps\libffi\src\x86\ffi.c @ 421]
*** ERROR: Symbol file could not be found.  Defaulted to export symbols for node.exe - 
00000000`0035f570 00007ff7`5288bff4 ffi_bindings!FFI::FFICall+0x14f [c:\node_modules\ffi\src\ffi.cc @ 289]
00000000`0035f5f0 00007ff7`52889d56 node!uv_cancel+0x44674
...
In other words I crashed where I expected. No symbols for node though. I wonder where I could find them.

In either case, lesson here is that:
1) debugging native with node.js is easy.
2) writing native code as node module should be easy as well. Sample code is close and available.

XMLHttpRequest, simple node and continuous updates.

Here is an example of node.js script:
var http = require('http'),
    fileSystem = require('fs');

function f(req, res) {
    var body = 'hello world';
    console.log(req.url);
    if (req.url == "/asdasd") 
    {
        res.writeHead(200, {
            'Content-Type': 'text/html' });
        filePath = "a.html";
        var readStream = fileSystem.createReadStream(filePath);
        readStream.pipe(res);
    }
    else
    {     
        var i = 0;
        res.writeHead(200, {
            'Content-Type': 'text/txt' });
        var idinterval;
        idinterval = setInterval( function()
        {
             res.write('Hello World');
             console.log("sent" + i);
             i+=1; 
             if(i==10)
             {
                  res.end();
                  clearInterval(idinterval);
             }
        }
        ,100);
    }
}
http.createServer(f).listen(1339, '127.0.0.1');
console.log('Server running at http://127.0.0.1:1339/');

The idea here is to return a.html if 127.0.0.1:1339/asdasd is asked for, otherwise write Hello World and send them in .1 second intervals.

For a.html, I started with http://www.w3schools.com/ajax/ajax_example.asp and ended up with this:
<!DOCTYPE html>
<html>
<head>
<script>
function loadXMLDoc()
{
  var xmlhttp;
  xmlhttp=new XMLHttpRequest();
  xmlhttp.onreadystatechange=function()
  {
    document.getElementById("myDiv").innerHTML= xmlhttp.responseText;
  }
  
xmlhttp.open("GET","http://127.0.0.1:1339",true);
xmlhttp.send();
}
</script>
</head>
<body>

<div id="myDiv"><h2>Some text to be changed</h2></div>
<button type="button" onclick="loadXMLDoc()">Change Content</button>

</body>
</html>

What is the purpose of this? Well, to demonstrate you can send data over long lasting connection in xhr. Then you could split it in chunks and display it somehow, yet the solution is not very usable unless you are sending finite amount of data: the size of the responseText grows. There are some non-standard solutions for xhr for Firefox and could be for some later versions of Chrome, but as it stands xhr should not be used for this purpose without some improvements (like kill connection, for example).

Also xhr is limited to same origin policy: http://en.wikipedia.org/wiki/Same_origin_policy

The information is mostly duplication of things here: http://friendlybit.com/js/partial-xmlhttprequest-responses/
Just a little bit on node.js. Some slides: http://courseware.codeschool.com/node_slides.pdf
I have trouble using node.js sample web server together with XMLHttpRequest.

In other news: an app idea I thought of is already there: https://play.google.com/store/apps/details?id=com.movile.wp&hl=en