Matthew van Eerde's web log

  • Matthew van Eerde's web log

    Buffer size alignment and the audio period

    • 2 Comments

    I got an email from someone today, paraphrased below:

    Q: When I set the sampling frequency to 48 kHz, and ask Windows what the audio period is, I get exactly 10 milliseconds. When I set it to 44.1 kHz, I get very slightly over 10 milliseconds: 10.1587 milliseconds, to be precise. Why?
    A: Alignment.

    A while back I talked a bit about the WASAPI exclusive-mode alignment dance. Some audio drivers have a requirement that they deal in buffer sizes which are multiples of a certain byte size - for example, a common alignment restriction for HD Audio hardware is 128 bytes.

    A more general audio requirement is that buffer sizes be a multiple of the size of a PCM audio frame.
    For example, suppose the audio format of a stream is stereo 16-bit integer. A single PCM audio frame will be 2 * 2 = 4 bytes. The first two bytes will be the 16-bit signed integer with the sample value for the left channel; the last two bytes will be the right channel.
    As another example, suppose the audio format of a stream is 5.1 32-bit floating point. A single PCM audio frame will be 6 * 4 = 24 bytes. Each of the six channels are a four-byte IEEE floating-point value; the channel order in Windows will be {Left, Right, Center, Low-Frequency Effects, Side Left, Side Right}.

    The audio engine tries to run at as close to a 10 millisecond cadence as possible, subject to the two restrictions above. Given a "desired minimum interval" (in milliseconds), and a streaming format, and an "alignment requirement" in bytes, you can calculate the closest achievable interval (without going under the desired interval) as follows:

    Note: this only works for uncompressed formats
    aligned_buffer(desired_milliseconds, format, alignment_bytes)
        desired_frames = nearest_integer(desired_milliseconds / 1000.0 * format.nSamplesPerSec)
        alignment_frames = least_common_multiple(alignment_bytes, format.nBlockAlign) / format.nBlockAlign
        actual_frames = ceiling(desired_frames / alignment_frames) * alignment_frames
        actual_milliseconds = actual_frames / format.nSamplesPerSec * 1000.0

    Here's a table of the actual buffer size (in frames and milliseconds), given a few typical inputs:

    Desired (milliseconds) Format Alignment (bytes) Desired frames Alignment (frames) Actual (frames) Actual (milliseconds)
    10 44.1 kHz stereo 16-bit integer 128 441 32 448 10.16
    10 48 kHz stereo 16-bit integer 128 480 32 480 10
    10 44.1 kHz 5.1 16-bit integer 128 441 32 448 10.16
    10 48 kHz 5.1 16-bit integer 128 480 32 480 10
    10 44.1 kHz 5.1 24-bit integer 128 441 64 448 10.16
    10 48 kHz 5.1 24-bit integer 128 480 64 512 10.66

    So to be really precise, the buffer size is actually 640/63 = 10.158730 milliseconds.

  • Matthew van Eerde's web log

    An attempt to explain the twin prime conjecture to a five-year-old

    • 1 Comments

    Back in April, Zhang Yitang came up with a result that is a major step toward proving the twin prime conjecture that there are infinitely many primes p for which p + 2 is also prime.

    In a reddit.com/r/math thread on the subject, I made the following comment as an attempt to explain the twin prime conjecture to a five-year-old:

    ELI5 attempt at the twin prime conjecture

    Think of cookie parties.

    If you have 100 cookies, you could have a cookie party:

    • by yourself (you get all the cookies)
    • with two people (each person gets 50 cookies)
    • with four people (each person gets 25 cookies)
    • with five people (each person gets 20 cookies)
    • with ten people (each person gets ten cookies)
    • with 20 people (each person gets five cookies)
    • with 25 people (each person gets four cookies)
    • with 50 people (each person gets two cookies)
    • with 100 people (each person gets one cookie)

    If you're the only person at your party, it's a sad party.

    If everyone at the party gets only one cookie, it's a sad party.

    If someone gets more than someone else, it's a sad party.

    You don't want your party to be sad, so you have to be careful to have the right number of people to share your cookies.

    If you have two cookies, or three, or five, or seven, or eleven, then it's not possible to have a happy party. There's no "right number of people."

    People used to wonder whether you could be sure to have a happy party if you just had enough cookies. A famous person named Euclid figured out that, no matter how many cookies you had, even if it was, like, more than a million, you might be unlucky and have a sad number of cookies.

    If it's a birthday party, the birthday kid's mom might give the birthday kid an extra cookie. (Or they might get something else instead.) That would be OK.

    If it's a birthday party, then, yes, you can be sure to have a happy party if you just had enough cookies. In fact, even three cookies would be enough; you could have the birthday kid, and one friend; they would each have one cookie, and the birthday kid would get the extra one.

    But Sam and Jane have a problem. They're twins, and they always have the same birthday. One year they had 13 cookies, and it was a big problem. 13 is a sad number. Even if they both had an extra cookie, that would leave 11, and that is still a sad number.

    (If you allow the birthday kid to have two extra cookies, that would leave nine; they could invite one more person, give everyone three cookies, and then Sam and Jane could each have two extras. But this is not a happy party because the guests will get upset that the birthday kids got two extra cookies. I mean, come on!)

    Sam and Jane wondered whether they could be sure to have a happy party if they just had enough cookies.

    So they asked their mom, who is, like, super smart.

    But even she didn't know.

    In fact, no-one knows. They don't think so. But they're not, like, super-sure.

  • Matthew van Eerde's web log

    Grabbing the output of the Microsoft Speech API text-to-speech engine as audio data

    • 3 Comments

    A while ago I wrote a post on Implementing a "say" command using ISpVoice from the Microsoft Speech API which showed how to use Speech API to do text-to-speech, but was limited to playing the generated audio out of the default audio device.

    Recently on the Windows Pro Audio forums, user falven asked a question about how to grab the output of the text-to-speech engine as a stream for further processing.

    Here's how to do it.

    The key part is to use ISpStream::BindToFile to save the audio data to a .wav file, and ISpStream::SetBaseStream to save to a given IStream. Then call ISpVoice::SetOutput with the ISpStream, prior to calling ISpVoice::Speak.

                ISpStream *pSpStream = nullptr;
                hr = CoCreateInstance(
                    CLSID_SpStream, nullptr, CLSCTX_ALL,
                    __uuidof(ISpStream),
                    (void**)&pSpStream
                );
                if (FAILED(hr)) {
                    ERR(L"CoCreateInstance(ISpVoice) failed: hr = 0x%08x", hr);
                    return -__LINE__;
                }
                ReleaseOnExit rSpStream(pSpStream);
               
                if (File == where) {
                    hr = pSpStream->BindToFile(
                        file,
                        SPFM_CREATE_ALWAYS,
                        &SPDFID_WaveFormatEx,
                        &fmt,
                        0
                    );
                    if (FAILED(hr)) {
                        ERR(L"ISpStream::BindToFile failed: hr = 0x%08x", hr);
                        return -__LINE__;
                    }
                } else {
                    // stream
                    pStream = SHCreateMemStream(NULL, 0);
                    if (nullptr == pStream) {
                        ERR(L"SHCreateMemStream failed");
                        return -__LINE__;
                    }
                   
                    hr = pSpStream->SetBaseStream(
                        pStream,
                        SPDFID_WaveFormatEx,
                        &fmt
                    );
                    if (FAILED(hr)) {
                        ERR(L"ISpStream::SetBaseStream failed: hr = 0x%08x", hr);
                        return -__LINE__;
                    }
                }
               
                hr = pSpVoice->SetOutput(pSpStream, TRUE);
                if (FAILED(hr)) {
                    ERR(L"ISpVoice::SetOutput failed: hr = 0x%08x", hr);
                    return -__LINE__;
                }

    Updated source and binaries attached.

    Usage:

    >say.exe
    say "phrase" [--file <filename> | --stream]
    runs phrase through text-to-speech engine
    if --file is specified, writes to .wav file
    if --stream is specified, captures to a stream
    if neither is specified, plays to default output

    Here's how to generate a .wav file (uh.wav attached)

    >say.exe "uh" --file uh.wav
    Stream is 1

    And here's how to generate an output stream. The app consumes this and prints the INT16 sample values to the console. uh.txt attached.

    >say.exe "uh" --stream
    Stream is 1
           0        0;        0        0;        0        0;        0        0
           0        0;        0        0;        0        0;        0        0
    ...
          86       86;    -1052    -1052;    -2839    -2839;    -3774    -3774
       -4199    -4199;    -4581    -4581;    -4284    -4284;    -3640    -3640
       -3100    -3100;    -2011    -2011;     -393     -393;      533      533
    ...

  • Matthew van Eerde's web log

    How to dump Speech API object properties

    • 0 Comments

    Stamatis Pap asked in a forum thread how to use a Speech API ISpVoice with a non-default audio deviceThis MSDN article shows how to use SpEnumTokens to list all the currently active audio outputs, but the number and order of audio outputs is subject to change as things come and go, or as the default audio device changes.

    I spent some time poking around the Speech API documentation and discovered that each audio output object has a DeviceId string value which is the WASAPI endpoint ID; this is the way to recognize a given audio output rather than relying on enumeration order.

    As part of figuring this out, as a side effect I created a command-line tool to dump all the speech objects and all of their properties.

    Source and binaries attached.

    Pseudocode:


    for each object category in
        (audio outputs; audio inputs; voices; recognizers; etc.)
        SpEnumTokens(category)
        ISpEnumTokens::GetCount();

        for each token
            ISpEnumTokens::Next(1);

            SpGetDescription(ISpObjectToken);
            Log the description

            the ISpObjectToken is also an ISpDataKey
            the ISpDataKey may also contain subkeys
            log all subkeys and their values recursively
                using ISpDataKey::EnumKeys and ISpDataKey::OpenKey
            for each subkey including this one
                log all values in the ISpDataKey
                    using ISpDataKey::EnumValues and ISpDataKey::GetStringValue

    Here's the output on my system.  Note the audio output has a DeviceId string value which matches the WASAPI endpoint ID.

    >speech-attributes.exe

    -- SPCAT_AUDIOOUT --
      #1: [[Speakers] ([High Definition Audio Device])]
        Attributes
          Vendor = Microsoft
          Technology = MMSys
        (default) = [[Speakers] ([High Definition Audio Device])]
        CLSID = {A8C680EB-3D32-11D2-9EE7-00C04F797396}
        DeviceName = [[Speakers] ([High Definition Audio Device])]
        DeviceId = {0.0.0.00000000}.{c2cbdacb-a70d-4629-8368-542a00f5a4b0}

    -- SPCAT_AUDIOIN --

    -- SPCAT_VOICES --
      #1: Microsoft Zira Desktop - English (United States)
        Attributes
          Version = 10.4
          Language = 409
          Gender = Female
          Age = Adult
          SharedPronunciation =
          Name = Microsoft Zira Desktop
          Vendor = Microsoft
        (default) = Microsoft Zira Desktop - English (United States)
        LangDataPath = C:\Windows\Speech\Engines\TTS\en-US\MSTTSLocEnUS.dat
        VoicePath = C:\Windows\Speech\Engines\TTS\en-US\M1033ZIR
        409 = Microsoft Zira Desktop - English (United States)
        CLSID = {C64501F6-E6E6-451f-A150-25D0839BC510}

    -- SPCAT_RECOGNIZERS --

    -- SPCAT_APPLEXICONS --

    -- SPCAT_PHONECONVERTERS --
      #1: Simplified Chinese Phone Converter
        Attributes
          Language = 804
        (default) = Simplified Chinese Phone Converter
        PhoneMap = (lengthy value redacted)
        CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8}
      #2: English Phone Converter
        Attributes
          Language = 409
        (default) = English Phone Converter
        PhoneMap = (lengthy value redacted)
        CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8}
      #3: French Phone Converter
        Attributes
          Language = 40C
        (default) = French Phone Converter
        PhoneMap = (lengthy value redacted)
        CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8}
      #4: German Phone Converter
        Attributes
          Language = 407
        (default) = German Phone Converter
        PhoneMap = (lengthy value redacted)
        CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8}
      #5: Japanese Phone Converter
        Attributes
          Language = 411
          NumericPhones =
          NoDelimiter =
        (default) = Japanese Phone Converter
        PhoneMap = (lengthy value redacted)
        CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8}
      #6: Spanish Phone Converter
        Attributes
          Language = 40A;C0A
        (default) = Spanish Phone Converter
        PhoneMap = (lengthy value redacted)
        CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8}
      #7: Traditional Chinese Phone Converter
        Attributes
          Language = 404
          NumericPhones =
          NoDelimiter =
        (default) = Traditional Chinese Phone Converter
        PhoneMap = (lengthy value redacted)
        CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8}
      #8: Universal Phone Converter
        Attributes
          Language = (lengthy value redacted)
        (default) = Universal Phone Converter
        PhoneMap = (lengthy value redacted)
        CLSID = {9185F743-1143-4C28-86B5-BFF14F20E5C8}

    -- SPCAT_RECOPROFILES --
      None found.

     

  • Matthew van Eerde's web log

    Generating sample first names

    • 0 Comments

    I had a need to write a script that would give me a random first name.  I grabbed the top 200 first names for baby boys in the US from 2000-2009, and the same list for baby girls:

    http://www.ssa.gov/OACT/babynames/decades/names2000s.html

    Boys Girls
    Jacob Emily
    Michael Madison
    ... ...

    My initial implementation just printed out the name, but I quickly realized I needed to print out the gender if I wanted to talk about what the (fictitious) person did.  So I updated it to print out the gender as well.

    In the course of this I realized that some names appeared on both lists.  In particular they are:

    • Alexis
    • Angel
    • Jordan
    • Peyton
    • Riley

    The script is called like this:

    >perl -w name.pl
    Wesley (male)

    And here's the source:

    use strict;

    # prints a randomly chosen name

    sub read_words();

    my @words = read_words();
    print $words[ rand(@words) ];

    sub read_words() {
        my @words = <DATA>;

        chomp @words;

        return @words;
    }
    __DATA__
    Aaliyah (female)
    Aaron (male)
    Abby (female)
    Abigail (female)
    Abraham (male)
    Adam (male)
    Addison (female)
    Adrian (male)
    Adriana (female)
    Adrianna (female)
    Aidan (male)
    Aiden (male)
    Alan (male)
    Alana (female)
    Alejandro (male)
    Alex (male)
    Alexa (female)
    Alexander (male)
    Alexandra (female)
    Alexandria (female)
    Alexia (female)
    Alexis (female)
    Alexis (male)
    Alicia (female)
    Allison (female)
    Alondra (female)
    Alyssa (female)
    Amanda (female)
    Amber (female)
    Amelia (female)
    Amy (female)
    Ana (female)
    Andrea (female)
    Andres (male)
    Andrew (male)
    Angel (female)
    Angel (male)
    Angela (female)
    Angelica (female)
    Angelina (female)
    Anna (female)
    Anthony (male)
    Antonio (male)
    Ariana (female)
    Arianna (female)
    Ashley (female)
    Ashlyn (female)
    Ashton (male)
    Aubrey (female)
    Audrey (female)
    Austin (male)
    Autumn (female)
    Ava (female)
    Avery (female)
    Ayden (male)
    Bailey (female)
    Benjamin (male)
    Bianca (female)
    Blake (male)
    Braden (male)
    Bradley (male)
    Brady (male)
    Brandon (male)
    Brayden (male)
    Breanna (female)
    Brendan (male)
    Brian (male)
    Briana (female)
    Brianna (female)
    Brittany (female)
    Brody (male)
    Brooke (female)
    Brooklyn (female)
    Bryan (male)
    Bryce (male)
    Bryson (male)
    Caden (male)
    Caitlin (female)
    Caitlyn (female)
    Caleb (male)
    Cameron (male)
    Camila (female)
    Carlos (male)
    Caroline (female)
    Carson (male)
    Carter (male)
    Cassandra (female)
    Cassidy (female)
    Catherine (female)
    Cesar (male)
    Charles (male)
    Charlotte (female)
    Chase (male)
    Chelsea (female)
    Cheyenne (female)
    Chloe (female)
    Christian (male)
    Christina (female)
    Christopher (male)
    Claire (female)
    Cody (male)
    Colby (male)
    Cole (male)
    Colin (male)
    Collin (male)
    Colton (male)
    Conner (male)
    Connor (male)
    Cooper (male)
    Courtney (female)
    Cristian (male)
    Crystal (female)
    Daisy (female)
    Dakota (male)
    Dalton (male)
    Damian (male)
    Daniel (male)
    Daniela (female)
    Danielle (female)
    David (male)
    Delaney (female)
    Derek (male)
    Destiny (female)
    Devin (male)
    Devon (male)
    Diana (female)
    Diego (male)
    Dominic (male)
    Donovan (male)
    Dylan (male)
    Edgar (male)
    Eduardo (male)
    Edward (male)
    Edwin (male)
    Eli (male)
    Elias (male)
    Elijah (male)
    Elizabeth (female)
    Ella (female)
    Ellie (female)
    Emily (female)
    Emma (female)
    Emmanuel (male)
    Eric (male)
    Erica (female)
    Erick (male)
    Erik (male)
    Erin (female)
    Ethan (male)
    Eva (female)
    Evan (male)
    Evelyn (female)
    Faith (female)
    Fernando (male)
    Francisco (male)
    Gabriel (male)
    Gabriela (female)
    Gabriella (female)
    Gabrielle (female)
    Gage (male)
    Garrett (male)
    Gavin (male)
    Genesis (female)
    George (male)
    Gianna (female)
    Giovanni (male)
    Giselle (female)
    Grace (female)
    Gracie (female)
    Grant (male)
    Gregory (male)
    Hailey (female)
    Haley (female)
    Hannah (female)
    Hayden (male)
    Hector (male)
    Henry (male)
    Hope (female)
    Hunter (male)
    Ian (male)
    Isaac (male)
    Isabel (female)
    Isabella (female)
    Isabelle (female)
    Isaiah (male)
    Ivan (male)
    Jack (male)
    Jackson (male)
    Jacob (male)
    Jacqueline (female)
    Jada (female)
    Jade (female)
    Jaden (male)
    Jake (male)
    Jalen (male)
    James (male)
    Jared (male)
    Jasmin (female)
    Jasmine (female)
    Jason (male)
    Javier (male)
    Jayden (male)
    Jayla (female)
    Jazmin (female)
    Jeffrey (male)
    Jenna (female)
    Jennifer (female)
    Jeremiah (male)
    Jeremy (male)
    Jesse (male)
    Jessica (female)
    Jesus (male)
    Jillian (female)
    Jocelyn (female)
    Joel (male)
    John (male)
    Johnathan (male)
    Jonah (male)
    Jonathan (male)
    Jordan (female)
    Jordan (male)
    Jordyn (female)
    Jorge (male)
    Jose (male)
    Joseph (male)
    Joshua (male)
    Josiah (male)
    Juan (male)
    Julia (female)
    Julian (male)
    Juliana (female)
    Justin (male)
    Kaden (male)
    Kaitlyn (female)
    Kaleb (male)
    Karen (female)
    Karina (female)
    Kate (female)
    Katelyn (female)
    Katherine (female)
    Kathryn (female)
    Katie (female)
    Kayla (female)
    Kaylee (female)
    Kelly (female)
    Kelsey (female)
    Kendall (female)
    Kennedy (female)
    Kenneth (male)
    Kevin (male)
    Kiara (female)
    Kimberly (female)
    Kyle (male)
    Kylee (female)
    Kylie (female)
    Landon (male)
    Laura (female)
    Lauren (female)
    Layla (female)
    Leah (female)
    Leonardo (male)
    Leslie (female)
    Levi (male)
    Liam (male)
    Liliana (female)
    Lillian (female)
    Lilly (female)
    Lily (female)
    Lindsey (female)
    Logan (male)
    Lucas (male)
    Lucy (female)
    Luis (male)
    Luke (male)
    Lydia (female)
    Mackenzie (female)
    Madeline (female)
    Madelyn (female)
    Madison (female)
    Makayla (female)
    Makenzie (female)
    Malachi (male)
    Manuel (male)
    Marco (male)
    Marcus (male)
    Margaret (female)
    Maria (female)
    Mariah (female)
    Mario (male)
    Marissa (female)
    Mark (male)
    Martin (male)
    Mary (female)
    Mason (male)
    Matthew (male)
    Max (male)
    Maxwell (male)
    Maya (female)
    Mckenzie (female)
    Megan (female)
    Melanie (female)
    Melissa (female)
    Mia (female)
    Micah (male)
    Michael (male)
    Michelle (female)
    Miguel (male)
    Mikayla (female)
    Miranda (female)
    Molly (female)
    Morgan (female)
    Mya (female)
    Naomi (female)
    Natalia (female)
    Natalie (female)
    Nathan (male)
    Nathaniel (male)
    Nevaeh (female)
    Nicholas (male)
    Nicolas (male)
    Nicole (female)
    Noah (male)
    Nolan (male)
    Oliver (male)
    Olivia (female)
    Omar (male)
    Oscar (male)
    Owen (male)
    Paige (female)
    Parker (male)
    Patrick (male)
    Paul (male)
    Payton (female)
    Peter (male)
    Peyton (female)
    Peyton (male)
    Preston (male)
    Rachel (female)
    Raymond (male)
    Reagan (female)
    Rebecca (female)
    Ricardo (male)
    Richard (male)
    Riley (female)
    Riley (male)
    Robert (male)
    Ruby (female)
    Ryan (male)
    Rylee (female)
    Sabrina (female)
    Sadie (female)
    Samantha (female)
    Samuel (male)
    Sara (female)
    Sarah (female)
    Savannah (female)
    Sean (male)
    Sebastian (male)
    Serenity (female)
    Sergio (male)
    Seth (male)
    Shane (male)
    Shawn (male)
    Shelby (female)
    Sierra (female)
    Skylar (female)
    Sofia (female)
    Sophia (female)
    Sophie (female)
    Spencer (male)
    Stephanie (female)
    Stephen (male)
    Steven (male)
    Summer (female)
    Sydney (female)
    Tanner (male)
    Taylor (female)
    Thomas (male)
    Tiffany (female)
    Timothy (male)
    Travis (male)
    Trenton (male)
    Trevor (male)
    Trinity (female)
    Tristan (male)
    Tyler (male)
    Valeria (female)
    Valerie (female)
    Vanessa (female)
    Veronica (female)
    Victor (male)
    Victoria (female)
    Vincent (male)
    Wesley (male)
    William (male)
    Wyatt (male)
    Xavier (male)
    Zachary (male)
    Zoe (female)
    Zoey (female)

  • Matthew van Eerde's web log

    Programmatically adding a folder to a shell library (e.g., the Music library)

    • 0 Comments

    I wrote a selfhost tool which allows me to add a folder (for example, C:\music) to a shell library (for example, the Music library.)

    This was before I found out about the shlib shell library sample which Raymond Chen blogged about.  If you're looking for a sample on how to manipulate shell libraries, prefer that one to this.

    Pseudocode:

    CoInitialize
    pShellLibrary = SHLoadLibraryFromKnownFolder(library GUID)
    SHAddFolderPathToLibrary(pShellLibrary, path)
    pShellLibrary->Commit()
    CoUninitialize

    Usage:

    >shelllibrary
    shelllibrary add <path> to <library>
        <path> must already exist
        <library> must be one of:
            documents
            music
            pictures
            videos
            recorded tv
    >shelllibrary add C:\music to Music
    Added C:\music to Music library

    Source and binaries attached.

  • Matthew van Eerde's web log

    Changing the desktop wallpaper using IDesktopWallpaper

    • 1 Comments

    About a year ago I wrote about how to change the desktop wallpaper using SystemParametersInfo(SPI_SETDESKWALLPAPER).

    Windows 8 desktop apps (not Store apps) can use the new IDesktopWallpaper API to get a more fine level of control.  So I wrote an app which uses the new API, though I just set the background on all monitors to the same image path, and I don't exercise any of the advanced features of the API.

    Pseudocode:

    CoInitialize
    CoCreateInstance(DesktopWallpaper)
    pDesktopWallpaper->SetWallpaper(NULL, full-path-to-image-file)
    pDesktopWallpaper->Release()
    CoUninitialize

    Usage:

    >desktopwallpaper.exe "%userprofile%\pictures\theda-bara.bmp"
    Setting the desktop wallpaper to C:\Users\MatEer\pictures\theda-bara.bmp succeeded.

    Source and binaries attached

  • Matthew van Eerde's web log

    Grabbing large amounts of text from STDIN in O(n) time

    • 0 Comments

    Last time I blogged about an O(n log n) solution to finding the longest duplicated substring in a given piece of text; I have since found an O(n) algorithm, which I linked to in the comments.

    But my blog post used an O(n2) algorithm to read the text from STDIN! It looked something like this:

    while (!done) {
        grab 2 KB of text
        allocate a new buffer which is 2 KB bigger
        copy the old text and the new text together into the new buffer
        free the old buffer
    }

    There are two better algorithms:

    while (!done) {
        grab an amount of text equal to the amount we've grabbed so far
        allocate a new buffer which is twice as large as the last buffer
        copy the old text and the new text together into the new buffer
        free the old buffer
    }

    And:

    while (!done) {
        grab 2 KB of text
        add this to the end of a linked list of text chunks
    }

    allocate a buffer whose size is the total size of all the chunks added together
    walk the linked list and copy the text of each chunk into the buffer

    Both "better" algorithms are O(n) but the latter wastes less space.

    Here's the improved code:

    struct Chunk {
        WCHAR text[1024];
        Chunk *next;
       
        Chunk() : next(nullptr) { text[0] = L'\0'; }
    };

    class DeleteChunksOnExit {
    public:
        DeleteChunksOnExit() : m_p(nullptr) {}
        ~DeleteChunksOnExit() {
            Chunk *here = m_p;
            while (here) {
                Chunk *next = here->next;
                delete here;
                here = next;
            }
        }
        void Set(Chunk *p) { m_p = p; }
       
    private:
        Chunk *m_p;
    };

    ...

    LPWSTR ReadFromStdIn() {
        Chunk *head = nullptr;
        Chunk *tail = nullptr;

        DeleteChunksOnExit dcoe;
       
        size_t total_length = 0;
       
        bool done = false;
        while (!done) {
            Chunk *buffer = new Chunk();
            if (nullptr == buffer) {
                LOG(L"Could not allocate memory for buffer");
                return nullptr;
            }
           
            if (nullptr == head) {
                // this runs on the first pass only
                head = buffer;
                tail = buffer;
                dcoe.Set(buffer);
            } else {
                tail->next = buffer;
                tail = buffer;
            }
           
            if (fgetws(buffer->text, ARRAYSIZE(buffer->text), stdin)) {
                total_length += wcslen(buffer->text);
            } else if (feof(stdin)) {
                done = true;
            } else {
                LOG(L"Error reading from STDIN");
                return nullptr;
            }
        }
       
        // gather all the allocations into a single string
        size_t size = total_length + 1;
        WCHAR *text = new WCHAR[size];
        if (nullptr == text) {
            LOG(L"Could not allocate memory for text");
            return nullptr;
        }
        DeleteArrayOnExit<WCHAR> deleteText(text);
       
        WCHAR *temp = text;
        for (Chunk *here = head; here; here = here->next) {
            if (wcscpy_s(temp, size, here->text)) {
                LOG(L"wcscpy_s returned an error");
                return nullptr;
            }
           
            size_t len = wcslen(here->text);
            temp += len;
            size -= len;
        }
       
        deleteText.Cancel();
        return text;
    }

  • Matthew van Eerde's web log

    Finding the longest substring which occurs twice in a given string

    • 2 Comments

    I'm reading Jon Bentley's Programming Pearls and one of the interesting exercises was to find the longest substring which occurs twice in a given string of length n.

    There's a naïve solution where you look at every pair of (distinct) indexes (i, j), and calculate the length of the common prefix of the substrings starting at those locations; this is O(n2) assuming that the length of the eventual maximum substring is O(1) (that is, << n.)

    Jon shows that there is an O(n log n) algorithm, which is a significant savings if n is large (e.g., War and Peace.)  This involves building an array of all substrings, then sorting them lexically, then walking the sorted array; the trick is that now we only need to check pairs of indexes that correspond to adjacent entries in the array.  That step can be done in O(n) time; the O(n log n) comes from the sorting step.

    I wrote up a quick app that implements his suggested algorithm.  Source follows.

    // main.cpp

    #include <windows.h>
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <search.h>

    #define LOG(format, ...) wprintf(format L"\n", __VA_ARGS__)

    template<typename T>
    class DeleteArrayOnExit {
    public:
        DeleteArrayOnExit(T *p) : m_p(p), m_canceled(false) {}
        ~DeleteArrayOnExit() { if (!m_canceled) { delete [] m_p; } }
        void Cancel() { m_canceled = true; }
        void Swap(T *p) { m_p = p; }
    private:
        T *m_p;
        bool m_canceled;
    };

    // caller must delete [] the buffer when done with it
    LPWSTR ReadFromStdIn();
    int __cdecl pwcscmp(const void *pstra, const void *pstrb) {
        return wcscmp(*(LPWSTR*)pstra, *(LPWSTR*)pstrb);
    }

    // returns length of longest common substring
    // don't include the null terminator if both strings are identical
    // e.g., comlen(banana, bananas) == comlen(banana, banana) == 6
    int comlen(LPCWSTR a, LPCWSTR b) {
        int i = 0;

        // keep going while the strings are the same and not ended
        while (a[i] && (a[i] == b[i])) { i++; }

        return i;
    }

    int _cdecl wmain() {
        LPWSTR text = ReadFromStdIn();
        if (nullptr == text) {
            return -__LINE__;
        }
        DeleteArrayOnExit<WCHAR> deleteText(text);
       
        size_t size = wcslen(text) + 1;
        LPWSTR *suffixes = new LPWSTR[size];
        if (nullptr == suffixes) {
            LOG(L"Could not allocate memory for suffixes");
            return -__LINE__;
        }
        DeleteArrayOnExit<LPWSTR> deleteSuffixes(suffixes);
       
        for (size_t i = 0; i < size; i++) {
            suffixes[i] = &text[i];
        }
       
        qsort(suffixes, size, sizeof(LPWSTR), pwcscmp);
       
        // find the longest common adjacent pair
        LPWSTR szMax = suffixes[0];
        size_t lenMax = 0;
        for (size_t i = 0; i < size - 1; i++) {
            size_t len = comlen(suffixes[i], suffixes[i + 1]);
            if (len > lenMax) {
                lenMax = len;
                szMax = suffixes[i];
            }
        }
       
        WCHAR *substring = new WCHAR[lenMax + 1];
        if (nullptr == substring) {
            LOG(L"Could not allocate memory for substring");
            return -__LINE__;
        }
        DeleteArrayOnExit<WCHAR> deleteSubstring(substring);
        if (0 != wcsncpy_s(substring, lenMax + 1, szMax, lenMax)) {
            LOG(L"wcsncpy_s failed");
            return -__LINE__;
        }
        substring[lenMax] = L'\0';
       
        // intentionally not using LOG to avoid trailing newline
        wprintf(L"%s", substring);
       
        return 0;
    }

    LPWSTR ReadFromStdIn() {
        WCHAR *text = new WCHAR[1];
        if (nullptr == text) {
            LOG(L"Could not allocate memory for text");
            return nullptr;
        }
        DeleteArrayOnExit<WCHAR> deleteText(text);
        text[0] = L'\0';

        // read a 2 KB chunk
        const size_t buffer_size = 1024;
        WCHAR *buffer = new WCHAR[buffer_size];
        if (nullptr == buffer) {
            LOG(L"Could not allocate memory for buffer");
            return nullptr;
        }
        DeleteArrayOnExit<WCHAR> deleteBuffer(buffer);
       
        bool done = false;
        do {
            if (fgetws(buffer, buffer_size, stdin)) {
                size_t size = wcslen(text) + wcslen(buffer) + 1;
                WCHAR *new_text = new WCHAR[size];
                if (nullptr == new_text) {
                    LOG(L"Could not allocate memory for new text");
                    return nullptr;
                }
                DeleteArrayOnExit<WCHAR> deleteNewText(new_text);
               
                WCHAR *dest = new_text;
               
                if (0 != wcscpy_s(dest, size, text)) {
                    LOG(L"wcscpy_s failed");
                    return nullptr;
                }
                dest += wcslen(text);
                size -= wcslen(text);
               
                if (0 != wcscpy_s(dest, size, buffer)) {
                    LOG(L"wcscpy_s failed");
                    return nullptr;
                }

                // that should do it for copying
                // now swap new_text => text
               
                delete [] text;
                text = new_text;

                deleteText.Swap(new_text);
                deleteNewText.Cancel();
               
            } else if (feof(stdin)) {
                done = true;
            } else {
                LOG(L"Error reading from STDIN");
                return nullptr;
            }
        } while (!done);
       
        deleteText.Cancel();
        return text;
    }

     

  • Matthew van Eerde's web log

    Enumerating mixer devices, mixer lines, and mixer controls

    • 0 Comments

    The WinMM multimedia APIs include an API for enumerating and controlling all the paths through the audio device; things like bass boost, treble control, pass-through audio from your CD player to your headphones, etc.  This is called the "mixer" API and is the forerunner of the IDeviceTopology API.

    I wrote a quick app to enumerate all the mixer devices on the system; for each mixer device, enumerate each mixer line (that is, each source and destination); for each mixer line, enumerate all the controls (volume, mute, equalization, etc.); and for each control, query the associated text (if any) and the current value.

    Source and binaries attached.

    Pseudocode:

    mixerGetNumDevs()
    for each mixer device
        mixerGetDevCaps(dev)
        for each destination (line) on the device
            mixerGetLineInfo(dest)
            mixerGetLineControls(dest)
            for each control on the line
                if the control supports per-item description
                    mixerGetControlDetails(control, MIXER_GETCONTROLDETAILSF_LISTTEXT)
                    log the per-item description
                mixerGetControlDetails(control, MIXER_GETCONTROLDETAILSF_VALUE)
                log the value(s)

    Usage:

    >mixerenum.exe
    Mixer devices: 5
    -- 0: Contoso headset --
        Device ID: 0
        Manufacturer identifier: 1
        Product identifier: 104
        Driver version: 6.2
        Product name: Contoso headset
        Support: 0x0
        Destinations: 1
            -- Destination 0: Master Volume --
                Destination: 0
                Source: -1
                Line ID: 0xffff0000
                Status: MIXERLINE_LINEF_ACTIVE (1)
                User: 0x00000000
                Component Type: MIXERLINE_COMPONENTTYPE_DST_HEADPHONES (5)
                Channels: 1
                Connections: 2
                Controls: 2
                Short name: Volume
                Long name: Master Volume
                -- Target:  --
                    Type: MIXERLINE_TARGETTYPE_UNDEFINED (0)
                    Device ID: 0
                    Manufacturer identifier: 65535
                    Product identifier: 65535
                    Driver version: 0.0
                    Product name:
                -- Control 1: Mute --
                    Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002)
                    Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
                    Item count: 0
                    Short name: Mute
                    Long name: Mute
                    -- Values --
                        FALSE
                -- Control 2: Volume --
                    Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001)
                    Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
                    Item count: 0
                    Short name: Volume
                    Long name: Volume
                    -- Values --
                        0xffff on a scale of 0x0 to 0xffff
    -- 1: HDMI Audio (Contoso --
        Device ID: 1
        Manufacturer identifier: 1
        Product identifier: 104
        Driver version: 6.2
        Product name: HDMI Audio (Contoso
        Support: 0x0
        Destinations: 1
            -- Destination 0: Master Volume --
                Destination: 0
                Source: -1
                Line ID: 0xffff0000
                Status: MIXERLINE_LINEF_ACTIVE (1)
                User: 0x00000000
                Component Type: MIXERLINE_COMPONENTTYPE_DST_DIGITAL (1)
                Channels: 1
                Connections: 2
                Controls: 2
                Short name: Volume
                Long name: Master Volume
                -- Target:  --
                    Type: MIXERLINE_TARGETTYPE_UNDEFINED (0)
                    Device ID: 0
                    Manufacturer identifier: 65535
                    Product identifier: 65535
                    Driver version: 0.0
                    Product name:
                -- Control 1: Mute --
                    Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002)
                    Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
                    Item count: 0
                    Short name: Mute
                    Long name: Mute
                    -- Values --
                        FALSE
                -- Control 2: Volume --
                    Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001)
                    Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
                    Item count: 0
                    Short name: Volume
                    Long name: Volume
                    -- Values --
                        0xffff on a scale of 0x0 to 0xffff
    -- 2: Speakers (Contoso --
        Device ID: 2
        Manufacturer identifier: 1
        Product identifier: 104
        Driver version: 6.2
        Product name: Speakers (Contoso
        Support: 0x0
        Destinations: 1
            -- Destination 0: Master Volume --
                Destination: 0
                Source: -1
                Line ID: 0xffff0000
                Status: MIXERLINE_LINEF_ACTIVE (1)
                User: 0x00000000
                Component Type: MIXERLINE_COMPONENTTYPE_DST_SPEAKERS (4)
                Channels: 1
                Connections: 2
                Controls: 2
                Short name: Volume
                Long name: Master Volume
                -- Target:  --
                    Type: MIXERLINE_TARGETTYPE_UNDEFINED (0)
                    Device ID: 0
                    Manufacturer identifier: 65535
                    Product identifier: 65535
                    Driver version: 0.0
                    Product name:
                -- Control 1: Mute --
                    Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002)
                    Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
                    Item count: 0
                    Short name: Mute
                    Long name: Mute
                    -- Values --
                        FALSE
                -- Control 2: Volume --
                    Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001)
                    Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
                    Item count: 0
                    Short name: Volume
                    Long name: Volume
                    -- Values --
                        0xffff on a scale of 0x0 to 0xffff
    -- 3: Contoso headset --
        Device ID: 3
        Manufacturer identifier: 1
        Product identifier: 104
        Driver version: 6.2
        Product name: Contoso headset
        Support: 0x0
        Destinations: 1
            -- Destination 0: Master Volume --
                Destination: 0
                Source: -1
                Line ID: 0xffff0000
                Status: MIXERLINE_LINEF_ACTIVE (1)
                User: 0x00000000
                Component Type: MIXERLINE_COMPONENTTYPE_DST_WAVEIN (7)
                Channels: 1
                Connections: 1
                Controls: 2
                Short name: Volume
                Long name: Master Volume
                -- Target: Contoso headset --
                    Type: MIXERLINE_TARGETTYPE_WAVEIN (2)
                    Device ID: 0
                    Manufacturer identifier: 1
                    Product identifier: 101
                    Driver version: 6.2
                    Product name: Contoso headset
                -- Control 1: Mute --
                    Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002)
                    Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
                    Item count: 0
                    Short name: Mute
                    Long name: Mute
                    -- Values --
                        FALSE
                -- Control 2: Volume --
                    Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001)
                    Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
                    Item count: 0
                    Short name: Volume
                    Long name: Volume
                    -- Values --
                        0xf332 on a scale of 0x0 to 0xffff
    -- 4: Microphone (Contoso --
        Device ID: 4
        Manufacturer identifier: 1
        Product identifier: 104
        Driver version: 6.2
        Product name: Microphone (Contoso
        Support: 0x0
        Destinations: 1
            -- Destination 0: Master Volume --
                Destination: 0
                Source: -1
                Line ID: 0xffff0000
                Status: MIXERLINE_LINEF_ACTIVE (1)
                User: 0x00000000
                Component Type: MIXERLINE_COMPONENTTYPE_DST_WAVEIN (7)
                Channels: 1
                Connections: 1
                Controls: 2
                Short name: Volume
                Long name: Master Volume
                -- Target: Microphone (Contoso --
                    Type: MIXERLINE_TARGETTYPE_WAVEIN (2)
                    Device ID: 1
                    Manufacturer identifier: 1
                    Product identifier: 101
                    Driver version: 6.2
                    Product name: Microphone (Contoso
                -- Control 1: Mute --
                    Type: MIXERCONTROL_CONTROLTYPE_MUTE (0x20010002)
                    Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
                    Item count: 0
                    Short name: Mute
                    Long name: Mute
                    -- Values --
                        FALSE
                -- Control 2: Volume --
                    Type: MIXERCONTROL_CONTROLTYPE_VOLUME (0x50030001)
                    Status: MIXERCONTROL_CONTROLF_UNIFORM (0x1)
                    Item count: 0
                    Short name: Volume
                    Long name: Volume
                    -- Values --
                        0xf332 on a scale of 0x0 to 0xffff


  • Matthew van Eerde's web log

    Enumerating MIDI devices

    • 0 Comments

    In addition to audio playback and recording, Windows Multimedia (WinMM) provides a Musical Instrument Digital Interface (MIDI) API.

    Here's how to make a list of all the MIDI devices on the system, their capabilities, and the hardware device interface associated with each of them.

    Source and binaries attached.

    Pseudocode:

    midiInGetNumDevs or midiOutGetNumDevs
    for each device
        midiInGetDevCaps or midiOutGetDevCaps
        log device capabilities
        midiInMessage or midiOutMessage
            with DRV_QUERYDEVICEINTERFACESIZE
            and DRV_QUERYDEVICEINTERFACE
        log the device interface

    Output:

    >midienum.exe
    midiIn devices: 1
    -- 0: USB2.0 MIDI Device --
        Device ID: 0
        Manufacturer identifier: 65535
        Product identifier: 65535
        Driver version: 1.6
        Product name: USB2.0 MIDI Device
        Support: 0x0
        Device interface: "\\?\usb#vid_xxxx&pid_yyyy&..."
    midiOut devices: 2
    -- 0: Microsoft GS Wavetable Synth --
        Device ID: 0
        Manufacturer identifier: 1
        Product identifier: 27
        Driver version: 1.0
        Product name: Microsoft GS Wavetable Synth
        Technology: 7 (MOD_SWSYNTH)
        Voices: 32
        Notes: 32
        Channel mask: 0xffff
        Support: 0x1
            MIDICAPS_VOLUME
        Device interface: ""
    -- 1: USB2.0 MIDI Device --
        Device ID: 1
        Manufacturer identifier: 65535
        Product identifier: 65535
        Driver version: 1.6
        Product name: USB2.0 MIDI Device
        Technology: 1 (MOD_MIDIPORT)
        Voices: 0
        Notes: 0
        Channel mask: 0xffff
        Support: 0x0
        Device interface: "\\?\usb#vid_xxxx&pid_yyyy&..."

    (Actual device interface string suppressed.)

    Note the Microsoft GS Wavetable Synth device, which is always present.

    Why would you want to know the device interface? In our case, because we want to test all the audio-related interfaces of a particular device on the system.

  • Matthew van Eerde's web log

    Implementing a "listen" command using ISpRecoContext from the Microsoft Speech API

    • 2 Comments

    Earlier today I posted a quick "say.exe" sample app which you give text and it speaks the text aloud using the text-to-speech part of the Windows Speech API.  It was very straightforward - only 67 lines of C++ code.

    It took me a little longer to figure out how to do this "listen.exe" sample app; you run it, speak into the microphone, and it uses the speech-to-text part of the Windows Speech API to print what you're saying to the console.  This is a little more involved: 202 lines of C++ code.

    Pseudocode:

    CoInitialize()
    CoCreateInstance(ISpRecoContext)
    pSpRecoContext->SetInterest(recognition events only, thanks)
    pSpRecoContext->CreateGrammar()
    pSpRecoGrammar->LoadDictation()
    pSpRecoGrammar->SetDictationState(active)
    while(...) {
        wait for a speech event (or the user to press Enter)
        pSpRecoContext->GetEvents()
        for each speech event {
            make sure SPEVENT.eEventId is SPEI_RECOGNITION
            event.lParam is an ISpRecoResult
            pSpRecoResult->GetText()
            print the text
        }
    }

    Usage:

    >listen.exe
    Speak into the microphone naturally; I will print what I understand.
    Press ENTER to quit.
    (At this point you start talking into the microphone. Text shows up here shortly after you say it.)

    Source and binaries attached.

  • Matthew van Eerde's web log

    Implementing a "say" command using ISpVoice from the Microsoft Speech API

    • 0 Comments

    I've known for a while that Microsoft Windows comes with text-to-speech and speech-to-text APIs, which power the Narrator and Speech Recognition features respectively.

    This forum post prompted me to mess around with them a little.

    I came up with this implementation of a say.exe command which takes a single argument as text, and then uses the ISpVoice text-to-speech API to have the computer speak it aloud.

    Source and binaries attached.

    Pseudocode:

    CoInitialize(nullptr);
    CoCreateInstance(ISpVoice)
    pSpVoice->Speak(text);

    Usage:

    >say.exe "Daisy, Daisy; give me your answer, do."

    More information on the Speech APIs available here: http://msdn.microsoft.com/en-us/library/ms723627(v=vs.85).aspx

  • Matthew van Eerde's web log

    Muting all audio outputs with IAudioEndpointVolume

    • 0 Comments

    I have a selfhost tool that I use to mute all audio outputs programmatically.

    Pseudocode:

    IMMDeviceEnumerator::EnumAudioEndpoints
    for each device:
        IMMDevice::Activate(IAudioEndpointVolume)
        IAudioEndpointVolume::SetMute(TRUE)

    Source and binaries attached.

  • Matthew van Eerde's web log

    Getting audio peak meter values for all active audio sessions

    • 7 Comments

    The Windows Vista volume mixer shows a peak meter for the device.  In Windows 7 we added a peak meter for each application.

    The audio interface for both is IAudioMeterInformation; I've used this before in my post about the linearity of Windows volume APIs.  This post showed how an application can get the peak meter reading for the device meter.

    In Windows 7 we also added APIs to allow applications to get a list of audio sessions.  I wrote up a quick app which shows how to get a list of all audio sessions, filter it down to the active ones (sessions which have an active audio client), and then get a peak meter reading.

    >meters.exe
    {0.0.0.00000000}.{c05f2f54-7294-422a-bb0d-8d690c365b73}|#%b{917F8618-9C57-4720-9B7C-88CA45FC983B}: 0.215705
    Active sessions: 1

    {0.0.0.00000000}.{c05f2f54-7294-422a-bb0d-8d690c365b73}|#%b{917F8618-9C57-4720-9B7C-88CA45FC983B} is the session identifier, which should be considered opaque.  0.215705 is the value of the peak meter, ranging from 0 to 1 linearly in amplitude.  If you are populating a visual peak meter with this information, you will need to apply a curve.

    Source and binaries attached.  Pseudocode follows:

    CoCreate(IMMDeviceEnumerator);
    IMMDeviceEnumerator::GetDefaultAudioEndpoint;
    IMMDevice::Activate(IAudioSessionManager2);
    IAudioSessionManager2::GetSessionEnumerator;
    for (each session) {
        IAudioSessionEnumerator::GetSession
        IAudioSessionControl::GetState
        if the state is anything but "active", skip to the next session
        QI IAudioSessionControl to IAudioSessionControl2
        IAudioSessionControl2::GetSessionIdentifier
        QI IAudioSessionControl to IAudioMeterInformation
        IAudioMeterInformation::GetPeakValue
        Log the session identifier and the peak value
    }

  • Matthew van Eerde's web log

    Windows Sound test team rowing morale event

    • 0 Comments

    Last Friday the Windows Sound test team went kayaking.  We went to the Agua Verde paddle club and kayaked around Union Bay for a while.

    Here's the route we took:

     

    More detail:

    http://connect.garmin.com/activity/179545084

     

  • Matthew van Eerde's web log

    Programmatically rearranging displays

    • 0 Comments

    Most of my test machines and my laptop have a single display; but I have two dev machines which are each connected to two displays.

    When I clean install Windows, I sometimes need to rearrange the displays:

    Since I clean install Windows frequently, I wrote myself a little C++ app which does this programmatically using EnumDisplayDevices / EnumDisplaySettings / ChangeDisplaySettingsEx.

    Source and binaries attached.

    Pseudocode:

    for (each device returned by EnumDisplayDevices) {

       grab the position and the height/width using EnumDisplaySettings

    }

    calculate the desired position of the secondary monitor

    Set it using ChangeDisplaySettingsEx with DM_POSITION

     

    Call as:

    >swapmonitors
    Moved secondary monitor to (1920, 0)

    EDIT: Oops: 0 should be CDS_GLOBAL | CDS_UPDATEREGISTRY, to make the settings apply to all users, and to persist across display resets / reboots

    LONG status = ChangeDisplaySettingsEx(
        nameSecondary,
        &mode,
        nullptr, // reserved
        CDS_GLOBAL | CDS_UPDATEREGISTRY, // was 0
        nullptr // no video parameter
    );

  • Matthew van Eerde's web log

    Weighing the Sun and the Moon

    • 0 Comments

    In an earlier post I mentioned how the Cavendish experiment allowed us to weigh the Earth - to determine the mass of the Earth mE.  Newton knew the acceleration due to gravity on the surface of the Earth and was able to use that to find the product G mE; Cavendish determined G directly, and was thus able to solve for mE.  He would also have been able to find the mass of the sun as follows:

    mE aE = G mE mS / rE2

    G, rE, and aE = vE2 / rE are known, so we can solve for mS.

    But calculating the mass of the moon is trickier.

    Once we were able to put a satellite around the moon we could measure its orbital radius and speed, deduce the acceleration, and use that plus the known G to calculate the mass of the moon.  But prior to that we were limited to techniques like:

    The moon does not exactly orbit the Earth, but instead orbits the center of mass of the moon/Earth system.  By careful observation we can determine where this center of mass is.  We can then measure the distance between the center of mass and the Earth's center.  This plus the known mass of the Earth and the distance of the Earth from the Moon allows us to determine the mass of the Moon.

    If we're lucky enough to see a foreign object come close to the moon, we can determine how much it is accelerated by the Moon.  This will allow us to determine the mass of the Moon using the technique above.  (We won't be able to determine the mass of the foreign object, but we don't need it.)

    When the USSR launched Sputnik, American scientists really wanted to know what its mass was.  But because none of the techniques above were useful, they were unable to determine it.

  • Matthew van Eerde's web log

    unattend.xml: turning on Remote Desktop automatically

    • 0 Comments

    Here are the portions of my unattend.xml file which are needed to turn on Remote Desktop automatically.

    This piece flips the "no remote desktop" kill switch to "allow."

        <settings pass="specialize">
            ...
            <component name="Microsoft-Windows-TerminalServices-LocalSessionManager" ...>
                <fDenyTSConnections>false</fDenyTSConnections>

    That's not enough; it is also necessary to poke a hole in the firewall to allow inbound connections.  I use an indirect string for the Group name, to allow for installing localized builds.  This points to the "Remote Desktop" feature group.

        <settings pass="specialize">
            ...
            <component name="Networking-MPSSVC-Svc" ...>
                <FirewallGroups>
                    <FirewallGroup wcm:action="add" wcm:keyValue="RemoteDesktop">
                        <Active>true</Active>
                        <Profile>all</Profile>
                        <Group>@FirewallAPI.dll,-28752</Group>

    If your user account is a member of the "Administrators" group, you're done:

        <settings pass="oobeSystem">
            <component name="Microsoft-Windows-Shell-Setup" ...>
                <UserAccounts>
                    <LocalAccounts>
                        <LocalAccount wcm:action="add">
                            <Password>
                                <Value>#PASSWORD_ADMIN#</Value>
                                <PlainText>true</PlainText>
                            </Password>
                            <Name>Admin</Name>
                            <Group>Administrators</Group>

    But if you're like me and you don't want to live in the Administrators group, you need to join the Remote Desktop Users group to be able to log in remotely:

        <settings pass="oobeSystem">
            <component name="Microsoft-Windows-Shell-Setup" ...>
                <UserAccounts>
                    <DomainAccounts>
                        <DomainAccountList wcm:action="add">
                            <Domain>redmond.corp.microsoft.com</Domain>
                            <DomainAccount wcm:action="add">
                                <Group>RemoteDesktopUsers</Group>
                                <Name>MatEer</Name>

  • Matthew van Eerde's web log

    Sample: how to enumerate waveIn and waveOut devices on your system

    • 4 Comments

    This shows how to call waveInGetNumDevs, waveInGetDevCaps, waveOutGetNumDevs, and waveOutGetDevCaps.

    // main.cpp

    #include <windows.h>
    #include <mmsystem.h>
    #include <stdio.h>

    #define LOG(format, ...) wprintf(format L"\n", __VA_ARGS__)

    int _cdecl wmain() {

        UINT devs = waveInGetNumDevs();
        LOG(L"waveIn devices: %u", devs);
        for (UINT dev = 0; dev < devs; dev++) {
            WAVEINCAPS caps = {};
            MMRESULT mmr = waveInGetDevCaps(dev, &caps, sizeof(caps));
           
            if (MMSYSERR_NOERROR != mmr) {
                 LOG(L"waveInGetDevCaps failed: mmr = 0x%08x", mmr);
                 return mmr;
            }
           
            LOG(
                L"-- waveIn device #%u --\n"
                L"Manufacturer ID: %u\n"
                L"Product ID: %u\n"
                L"Version: %u.%u\n"
                L"Product Name: %s\n"
                L"Formats: 0x%x\n"
                L"Channels: %u\n"
                L"Reserved: %u\n"
                ,
                dev,
                caps.wMid,
                caps.wPid,
                caps.vDriverVersion / 256, caps.vDriverVersion % 256,
                caps.szPname,
                caps.dwFormats,
                caps.wChannels,
                caps.wReserved1
            );
        }

        devs = waveOutGetNumDevs();
        LOG(L"waveOut devices: %u", devs);
        for (UINT dev = 0; dev < devs; dev++) {
            WAVEOUTCAPS caps = {};
            MMRESULT mmr = waveOutGetDevCaps(dev, &caps, sizeof(caps));
           
            if (MMSYSERR_NOERROR != mmr) {
                 LOG(L"waveOutGetDevCaps failed: mmr = 0x%08x", mmr);
                 return mmr;
            }
           
            LOG(
                L"-- waveOut device #%u --\n"
                L"Manufacturer ID: %u\n"
                L"Product ID: %u\n"
                L"Version: %u.%u\n"
                L"Product Name: %s\n"
                L"Formats: 0x%x\n"
                L"Channels: %u\n"
                L"Reserved: %u\n"
                L"Support: 0x%x\n"
                L"%s%s%s%s%s"
                ,
                dev,
                caps.wMid,
                caps.wPid,
                caps.vDriverVersion / 256, caps.vDriverVersion % 256,
                caps.szPname,
                caps.dwFormats,
                caps.wChannels,
                caps.wReserved1,
                caps.dwSupport,
                    ((caps.dwSupport & WAVECAPS_LRVOLUME) ?       L"\tWAVECAPS_LRVOLUME\n" :       L""),
                    ((caps.dwSupport & WAVECAPS_PITCH) ?          L"\tWAVECAPS_PITCH\n" :          L""),
                    ((caps.dwSupport & WAVECAPS_PLAYBACKRATE) ?   L"\tWAVECAPS_PLAYBACKRATE\n" :   L""),
                    ((caps.dwSupport & WAVECAPS_VOLUME) ?         L"\tWAVECAPS_VOLUME\n" :         L""),
                    ((caps.dwSupport & WAVECAPS_SAMPLEACCURATE) ? L"\tWAVECAPS_SAMPLEACCURATE\n" : L"")
            );
        }

        return 0;
    }

    On my system this outputs:

    waveIn devices: 3
    -- waveIn device #0 --
    Manufacturer ID: 1
    Product ID: 65535
    Version: 0.0
    Product Name: Microphone (High Definition Aud
    Formats: 0xfffff
    Channels: 2
    Reserved: 0

    -- waveIn device #1 --
    Manufacturer ID: 1
    Product ID: 65535
    Version: 0.0
    Product Name: Digital Audio (S/PDIF) (High De
    Formats: 0xfffff
    Channels: 2
    Reserved: 0

    -- waveIn device #2 --
    Manufacturer ID: 1
    Product ID: 65535
    Version: 0.0
    Product Name: CD Audio (High Definition Audio
    Formats: 0xfffff
    Channels: 2
    Reserved: 0

    waveOut devices: 2
    -- waveOut device #0 --
    Manufacturer ID: 1
    Product ID: 65535
    Version: 0.0
    Product Name: Headphones (High Definition Aud
    Formats: 0xfffff
    Channels: 2
    Reserved: 0
    Support: 0x2e
     WAVECAPS_LRVOLUME
     WAVECAPS_PLAYBACKRATE
     WAVECAPS_VOLUME
     WAVECAPS_SAMPLEACCURATE

    -- waveOut device #1 --
    Manufacturer ID: 1
    Product ID: 65535
    Version: 0.0
    Product Name: Digital Audio (S/PDIF) (High De
    Formats: 0xfffff
    Channels: 2
    Reserved: 0
    Support: 0x2e
     WAVECAPS_LRVOLUME
     WAVECAPS_PLAYBACKRATE
     WAVECAPS_VOLUME
     WAVECAPS_SAMPLEACCURATE

     

    Source and binaries attached.

  • Matthew van Eerde's web log

    How many numbers are straights?

    • 2 Comments

    As many people, I have to deal with a lot of numbers all the time (bug numbers, changelist numbers, tracking numbers, ...) and as a mathematician I sometimes notice when numbers have peculiar properties.

    For example, I recently ran into 152463, which is a straight (made up of consecutive digits, not necessarily in order.)  I then ran into 35426, which is also a straight.  Is this odd?

    To put it another way - what proportion of numbers are straights?

    We consider only non-negative integer numbers {0, 1, 2, ... }.  No duplicate digits are allowed, so the very last straight is 9,876,543,210.

    Break it down by the length of the number in digits.  For example, how many four-digit numbers are there?  We can choose any number from 1-9 for the first digit, and any number from 0-9 for each of the other three digits; so there are 9 * 103 numbers of length 4.

    How many of these are straights?  There are seven ways to choose a set of four consecutive digits to make up a four-digit straight: {0,1, 2, 3}, {1, 2, 3, 4}, {2, 3, 4, 5}, {3, 4, 5, 6}, {4, 5, 6, 7}, {5, 6, 7, 8}, {6, 7, 8, 9}.

    Each of these seven ways can then be shuffled to make the straights themselves.  For six of these seven sets of digits, all possible shufflings are allowed; there are 4! shufflings for each set.  This gives 6 * 4! straights.

    But for {0, 1, 2, 3}, we have to be careful not to end up with 0 as a leading digit.  We choose the leading digit first out of the set {1, 2, 3} (there are three ways to do this) and then we have complete freedom to shuffle the three remaining digits (including 0.)  This gives 3 * 3! straights.

    So there are 6 * 4! + 3 * 3! straights which are four digits long.

    Considering all possible lengths from 1 to 10 (we'll consider 0 as a number of length 1) gives the following table:

    Length Numbers Straights % Straights
    1 10 10 100.000%
    2 9 * 101 17 18.889%
    3 9 * 102 46 5.111%
    4 9 * 103 162 1.800%
    5 9 * 104 696 0.773%
    6 9 * 105 3480 0.387%
    7 9 * 106 19,440 0.216%
    8 9 * 107 115,920 0.129%
    9 9 * 108 685,440 0.076%
    10 9 * 109 3,265,920 0.036%
    Total 1010 40,91,131 0.041%

    Since roughly 1% of five-digit numbers are straights, it is not surprising that I see them that often.

  • Matthew van Eerde's web log

    My unattend.xml file

    • 5 Comments

    As a tester on Windows 8 I install Windows on my dev machine very frequently.

    I use F12 to boot from the network into WinPE, then I run a .bat file which looks something like this:

    @echo off
    setlocal enabledelayedexpansion

    set PASSWORD_ADMIN=(redacted)
    set PASSWORD_MATEER=(redacted)
    set LICENSE_KEY=(redacted)
    set FANCYLANG=qps-plocm

    del unattend-processed.xml
    for /f "usebackq delims=" %%l in (`type unattend-template.xml`) do (
        set line=%%l
        set line=!line:#PASSWORD_ADMIN#=%PASSWORD_ADMIN%!
        set line=!line:#PASSWORD_MATEER#=%PASSWORD_MATEER%!
        set line=!line:#LICENSE_KEY#=%LICENSE_KEY%!
        set line=!line:#FANCY_LANG#=%FANCY_LANG%!
        echo !line! >> unattend-processed.xml
    )

    setup.exe /unattend:unattend-processed.xml

    This takes my template unattend.xml file, injects various parameters, and calls setup.exe.

    The template unattend.xml follows in all of its glory.  We'll take a closer look at some of the things in future posts.

    <?xml version="1.0" encoding="utf-8"?>
    <unattend xmlns="urn:schemas-microsoft-com:unattend">
        <settings pass="windowsPE">
            <component name="Microsoft-Windows-Setup" processorArchitecture="amd64" publicKeyToken="31bf3856ad364e35" language="neutral" versionScope="nonSxS" xmlns:wcm="http://schemas.microsoft.com/WMIConfig/2002/State" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
                <UserData>
                    <ProductKey>
                        <WillShowUI>OnError</WillShowUI>
                        <Key>#LICENSE_KEY#</Key>
                    </ProductKey>
                    <AcceptEula>true</AcceptEula>
                    <FullName>Matthew van Eerde</FullName>
                    <Organization>Microsoft</Organization>
                </UserData>
                <DiskConfiguration>
                    <Disk wcm:action="add">
                        <CreatePartitions>
                            <CreatePartition wcm:action="add">
                                <Order>1</Order>
                                <Extend>true</Extend>
                                <Type>Primary</Type>
                            </CreatePartition>
                        </CreatePartitions>
                        <WillWipeDisk>true</WillWipeDisk>
                        <DiskID>0</DiskID>
                    </Disk>
                </DiskConfiguration>
                <ImageInstall>
                    <OSImage>
                        <WillShowUI>OnError</WillShowUI>
                        <InstallToAvailablePartition>true</InstallToAvailablePartition>
                    </OSImage>
                </ImageInstall>
            </component>
            <component name="Microsoft-Windows-International-Core-WinPE" processorArchitecture="amd64" publicKeyToken="31bf3856ad364e35" language="neutral" versionScope="nonSxS" xmlns:wcm="http://schemas.microsoft.com/WMIConfig/2002/State" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
                <SetupUILanguage>
                    <UILanguage>#FANCY_LANG#</UILanguage>
                </SetupUILanguage>
                <InputLocale>0409:00000409</InputLocale>
                <UserLocale>en-US</UserLocale>
                <SystemLocale>en-US</SystemLocale>
                <UILanguage>#FANCY_LANG#</UILanguage>
            </component>
        </settings>
        <settings pass="specialize">
            <component name="Microsoft-Windows-UnattendedJoin" processorArchitecture="amd64" publicKeyToken="31bf3856ad364e35" language="neutral" versionScope="nonSxS" xmlns:wcm="http://schemas.microsoft.com/WMIConfig/2002/State" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
                <Identification>
                    <Credentials>
                        <Domain>redmond.corp.microsoft.com</Domain>
                        <Password>#PASSWORD_MATEER#</Password>
                        <Username>MatEer</Username>
                    </Credentials>
                    <JoinDomain>ntdev.corp.microsoft.com</JoinDomain>
                </Identification>
            </component>
            <component name="Microsoft-Windows-Shell-Setup" processorArchitecture="amd64" publicKeyToken="31bf3856ad364e35" language="neutral" versionScope="nonSxS" xmlns:wcm="http://schemas.microsoft.com/WMIConfig/2002/State" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
                <ComputerName>MATEER-Q</ComputerName>
                <RegisteredOwner>Matthew van Eerde</RegisteredOwner>
                <RegisteredOrganization>Microsoft</RegisteredOrganization>
            </component>
            <component name="Microsoft-Windows-TerminalServices-LocalSessionManager" processorArchitecture="amd64" publicKeyToken="31bf3856ad364e35" language="neutral" versionScope="nonSxS" xmlns:wcm="http://schemas.microsoft.com/WMIConfig/2002/State" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
                <fDenyTSConnections>false</fDenyTSConnections>
            </component>
            <component name="Networking-MPSSVC-Svc" processorArchitecture="amd64" publicKeyToken="31bf3856ad364e35" language="neutral" versionScope="nonSxS" xmlns:wcm="http://schemas.microsoft.com/WMIConfig/2002/State" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
                <FirewallGroups>
                    <FirewallGroup wcm:action="add" wcm:keyValue="RemoteDesktop">
                        <Active>true</Active>
                        <Profile>all</Profile>
                        <Group>@FirewallAPI.dll,-28752</Group>
                    </FirewallGroup>
                </FirewallGroups>
            </component>
        </settings>
        <settings pass="oobeSystem">
            <component name="Microsoft-Windows-Shell-Setup" processorArchitecture="amd64" publicKeyToken="31bf3856ad364e35" language="neutral" versionScope="nonSxS" xmlns:wcm="http://schemas.microsoft.com/WMIConfig/2002/State" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
                <OOBE>
                    <HideEULAPage>true</HideEULAPage>
                    <NetworkLocation>Work</NetworkLocation>
                    <ProtectYourPC>3</ProtectYourPC>
                    <HideOnlineAccountScreens>true</HideOnlineAccountScreens>
                    <HideLocalAccountScreen>true</HideLocalAccountScreen>
                    <HideWirelessSetupInOOBE>true</HideWirelessSetupInOOBE>
                </OOBE>
                <UserAccounts>
                    <LocalAccounts>
                        <LocalAccount wcm:action="add">
                            <Password>
                                <Value>#PASSWORD_ADMIN#</Value>
                                <PlainText>true</PlainText>
                            </Password>
                            <Name>Admin</Name>
                            <Group>Administrators</Group>
                        </LocalAccount>
                    </LocalAccounts>
                    <DomainAccounts>
                        <DomainAccountList wcm:action="add">
                            <Domain>redmond.corp.microsoft.com</Domain>
                            <DomainAccount wcm:action="add">
                                <Group>RemoteDesktopUsers</Group>
                                <Name>MatEer</Name>
                            </DomainAccount>
                        </DomainAccountList>
                    </DomainAccounts>
                </UserAccounts>
                <TimeZone>Pacific Standard Time</TimeZone>
                <AutoLogon>
                    <Password>
                        <Value>#PASSWORD_MATEER#</Value>
                        <PlainText>true</PlainText>
                    </Password>
                    <Domain>redmond.corp.microsoft.com</Domain>
                    <Enabled>true</Enabled>
                    <LogonCount>1</LogonCount>
                    <Username>MatEer</Username>
                </AutoLogon>
            </component>
        </settings>
    </unattend>

     

  • Matthew van Eerde's web log

    Programmatically setting a local user account to never expire its password

    • 1 Comments

    As a Windows tester, I install Windows on my own machines a lot (this is known internally as "selfhosting", or "dogfooding", or "ice cream-ing".)

    One of my little idiosyncracies is I like to run as a non-administrative user.  That is, I don't add my domain account to the local Administrators group.

    Instead, I create a local "Admin" account with a known (to me) password; every time I need to elevate, I get a prompt that asks for credentials rather than just "Yes/No".  To this prompt I pass the credentials of the local "Admin" account.

    Although I usually install fresh builds regularly (on my multiple machines), sometimes one machine gets a little stale.  In fact, it happened once that my local .\Admin account got so stale that I had to change the password!  This was annoying enough that I devoted some energy into figuring out how to check the "Password never expires" box on the local account properties programmatically.

    The result was the following script: call as cscript.exe never-expire-admin-password.wsf  This version hardcodes the username "Admin"; a production version would probably allow passing a username in via the command line.

    If the Admin password already has the box checked, this script does nothing.

    ' LDAP doesn't work for controlling local users
    ' (unless you're a domain controller, of course)
    '
    ' have to use WinNT provider instead

    Const ADS_UF_DONT_EXPIRE_PASSWD = &H10000

    ' hardcoding "Admin" username
    Dim admin: Set admin = GetObject("WinNT://localhost/Admin,user")

    WScript.Echo "Admin's userFlags are 0x" & Hex(admin.userFlags)

    If Not admin.userFlags And ADS_UF_DONT_EXPIRE_PASSWD Then
        WScript.Echo "Setting local admin account to never expire password"
        admin.userFlags = (admin.userFlags Or ADS_UF_DONT_EXPIRE_PASSWD)

        ' Save
        admin.SetInfo
    End If

  • Matthew van Eerde's web log

    Teaching someone to fish and the AKS primality test

    • 0 Comments

    This morning my wife (whom I love and adore) woke me up at 3:00 AM with an urgent question.

    "Hey!" she said, shaking me awake.

    "Is 19 prime?"

    ...

    Like a fool, I answered her.  "Yes.  Yes it is."  Off she went.

    This is a true response, but not a correct response.  I realized shortly afterwards that a correct response would look more like:

    I'm glad you asked me that. dear.  Eratosthenes, the Greek mathematician, discovered a very efficient way to list primes in about 200 BC that is still in use today.  You start by writing out all the numbers from 1 to 19: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19.  1 is a very special number (it's the multiplicative identity, or what algebraists would call a unit) so we put a square around it.  The first number we didn't consider was 2, so we circle it - that means it's prime - and then cross out every multiple of 2 after that.  Going back, the first number we didn't consider was 3... and so on until we get 1 2 3 X 5 X 7 X X X 11 X 13 X X X 17 X 19.  A common optimization is to realize that after circling a prime p, the first number you cross out (that wasn't crossed out before) is always p2, which means that after circling a number you can immediately jump to its square, and also means you can stop crossing out altogether once you hit p> N...

    This would allow her to fish rather than waking me up when she wanted a fish.

    An even better response would have been:

    It's funny you've asked me that.  Number theorists and cryptanalysts have considered this question for thousands of years.  Eratosthenes' method (see above) is a very simple way to find all the primes below a given number, but an efficient way to determine whether a given number is prime was found only very recently.

    In practice, the test that is usually used is the randomized version of the Miller-Rabin test.  Although this is nondeterministic, it is very fast indeed, and will tell you to a very high degree of certainty whether the given number is prime.  This usually suffices.

    There is a deterministic version of the Miller-Rabin test too, which is guaranteed to tell you with perfect certainty whether the given number is prime.  But it only works if you believe in the generalized Riemann hypothesis.  Most mathematicians nowadays believe the hypothesis, but no-one has (yet) been able to prove it.

    Amazingly, in 2002 three mathematicians named Manindra Agrawal, Neeraj Kayal, and Nitin Saxena came up with a deterministic, proven, polynomial-time (specifically, polynomial in the number of digits in the input) method for telling whether a given number is prime.   This is known as the AKS primality test.  The most striking thing about this test is its simplicity - if something this straightforward can be found after thousands of years of looking, what else out there remains to be found?

    Such a response would probably prevent her from waking me again for any mathematical problem at all.  Boo-ya.

    Here's Agrawal, Kayal, and Saxena's "PRIMES is in P" paper.

    Here's Yves Gallot's C++ implementation of AKS.

    My own Perl implementation follows:

    use strict;
    # use bignum;

    print <<USAGE and exit 0 unless @ARGV;
    $0 [-v] n
        Use the AKS primality test to check whether n is prime
        -v adds verbose log spew
    USAGE

    sub is_power($$);
    sub ceil_log2($);
    sub first_r($$);
    sub check_gcds($$);
    sub check_polynomials($$$);
    sub gcd($$);
    sub totient($);
    sub polypow($$\@);
    sub polymult($$\@\@);
    sub polyeq(\@\@);

    my $verbose = $ARGV[0] eq "-v";
    shift @ARGV if $verbose;

    die "Expected only one argument" unless 1 == @ARGV;
    my $n = shift;

    # step 0: restrict to integers >= 2
    print "$n is not an integer and so is NEITHER PRIME NOR COMPOSITE\n" and exit 0 unless int($n) == $n;
    print "$n < 2 and so is NEITHER PRIME OR COMPOSITE\n" and exit 0 unless $n >= 2;

    # step 1: check if the number is a power of some lower number.
    # this can be done quickly by iterating over the exponent (2, 3, ...)
    # and doing a binary search on the base.
    # we start at the top and work down for performance reasons;
    # several subroutines need to know ceil(log2(n)) so we calculate it once and pass it around.
    my $log2_n = ceil_log2($n);
    is_power($n, $log2_n) and exit 0;
    print "Not a power.\n";

    # step 2: find the smallest r such that o_r(n) > (log2 n)^2
    # where o_r(n) is the multiplicative order of n mod r
    # that is, the smallest k such that n^k == 1 mod r
    my $r = first_r($n, $log2_n);
    print "r = $r\n";

    # step 3: for all a between 2 and r inclusive, check whether gcd(a, n) > 1
    check_gcds($n, $r) or exit 0;

    # step 4: if r >= n, we're done
    if ($r >= $n) {
        print "$r >= $n so $n is PRIME\n";
        exit 0;
    }

    # step 5: for all a between 1 and floor( sqrt(phi(r)) log2(n) )
    # check whether (x + a)^n = x^n + a mod x^r - 1, n
    check_polynomials($n, $r, $log2_n) or exit 0;

    # step 6: if we got this far, n is prime
    print "$n is PRIME\n";

    sub is_power($$) {
        my $n = shift;
        my $log2_n = shift; # actually ceil(log2(n))

        print "Checking for power-ness...\n";

        # we consider numbers of the form b^i
        # we iterate over the exponent i
        # starting at i = ceil(log2(n)) and working down to i = 2
        #
        # for each exponent we do a binary search on the base
        # the lowest the base can be is 2
        # and the highest the base can be (initially) is 2
        #
        # we set up bounds on the base that are guaranteed to
        # surround the actual base
        my $b_low = 1; # 1 ^ ceil(log2(n)) = 1 < n
        my $b_high = 3; # 3 ^ ceil(log2(n)) > 2 ^ log2(n) = n

        for (my $i = $log2_n; $i >= 2; $i--) {
            print "\tb^$i\n" if $verbose;

            # let's check that the bounds are really correct
            die "$b_low ^ $i is not < $n" unless $b_low ** $i < $n;
            die "$b_high ^ $i is not > $n" unless $b_high ** $i > $n;

            # do a binary search to find b such that b ^ i = n
            while ($b_high - $b_low > 1) {
                print "\t\tb^$i: b is between $b_low and $b_high\n" if $verbose;
                my $b = int(($b_low + $b_high)/2);

                my $t = $b ** $i;
                if ($t == $n) {
                    print "$n = $b^$i; $n is COMPOSITE\n";
                    return 1;
                }

                ($t > $n ? $b_high : $b_low) = $b;
            }

            # as we pass from the exponent (say, 5)
            # to the exponent below (say, 4)
            # we need to reconsider our bounds
            #
            # b_low can remain the same because b ^ (i - 1) is even less than b ^ i
            # OPEN ISSUE: can we even raise b_low?
            #
            # but we need to raise b_high since b ^ i > n does NOT imply b ^ (i - 1) > n
            #
            # we'll square b_high; b ^ i > n => (b ^ 2) ^ (i - 1) = b ^ (2 i - 2) > n
            # since i >= 2
            #
            # OPEN ISSUE: is there a better way to raise this higher bound? Does this help much?
            $b_high *= $b_high;
        }

        # nope, not a power
        return 0;
    }

    sub ceil_log2($) {
        my $n = shift;

        my $i = 0;
        my $t = 1;

        until ($t >= $n) {
            $i++;
            $t *= 2;
        }

        return $i;
    }

    sub first_r($$) {
        my $n = shift;
        my $log2_n = shift; # actually ceil(log2(n))

        my $s = $log2_n ** 2;
        print "Looking for the first r where o_r($n) > $s...\n";

        # for each r we want to find the smallest k such that
        # n^k == 1 mod r

        my $r;
        for ($r = 2; ; $r++) {
            # print "\tTrying $r...\n";

            # find the multiplicative order of n mod r
            my $k = 1;
            my $t = $n % $r;

            until (1 == $t or $k > $s) {
                $t = ($t * $n) % $r;
                $k++;
            }

            if ($k > $s) {
                # print "\to_$r($n) is at least $k\n";
                last;
            } else {
                # print "\to_$r($n) = $k\n";
            }
        }

        return $r;
    }

    sub check_gcds($$) {
        my ($n, $r) = @_;

        print "Checking GCD($n, a) for a = 2 to $r...\n";

        for (my $a = 2; $a <= $r; $a++) {
            my $g = gcd($n, $a);

            next if ($g == $n); # this is OK

            if (1 != $g) {
                print "gcd($n, $a) = $g; $n is COMPOSITE\n";
                return 0;
            }
        }

        print "All GCDs are 1 or $n\n";

        return 1;
    }

    sub gcd($$) {
        my ($x, $y) = @_;

        ($x, $y) = ($y, $x) unless $x > $y;

        while ($y) {
            ($x, $y) = ($y, $x % $y);
        }

        return $x;
    }

    sub check_polynomials($$$) {
        my $n = shift;
        my $r = shift;
        my $log2_n = shift; # actually ceil(log2(n))

        # iterate over a from 1 to floor( sqrt(phi(r)) log2(n) )
        # for each a, check whether the polynomial equality holds:
        # (x + a)^n = x^n + a mod (x^r - 1, n)
        # if it fails to hold, the number is composite
        #
        # first we need to evaluate phi(r) so we can determine the upper bound
        # OPEN ISSUE: this seems to be a potential weakness in the algorithm
        # because the usual way to evaluate phi(r) is to find the prime factorization of r
        # and then form the product r*PI(1 - 1/p) where the product ranges over all primes
        # which divide r

        my $phi = totient($r);

        # a < sqrt(phi(r)) * log2(n) => a^2 < phi(r) * (log2(n))^2
        my $a2_max = $phi * $log2_n * $log2_n;
        print "Checking polynomials up to roughly ", int sqrt($a2_max), "...\n";

        for (my $a = 1; $a * $a <= $a2_max; $a++) {
            print "\ta = $a...\n" if $verbose;

            # polynomials are of the form (c0, c1, c2, ..., ci, ...)
            # which corresponds to c0 + c1 x + c2 x^2 + ... + ci x^i + ...)
            my @x = (0, 1);
            my @x_plus_a = ($a % $n, 1);

            my @lhs = polypow($n, $r, @x_plus_a);

            # POTENTIAL OPTIMIZATION:
            # x^n + a mod (x^r - 1) is just x^(n % r) + a
            # and we know n % r != 0
            my @rhs = polypow($n, $r, @x); # x^n
            $rhs[0] = ($rhs[0] + $a) % $n; # + a

            next if polyeq(@lhs, @rhs);

            print "(x + $a)^$n is not equal to x^$n + $a mod(x^$r - 1, $n)\n";
            print "So $n is COMPOSITE\n";
            return 0;
        }

        return 1;
    }

    sub totient($) {
        my $r = shift;

        print "Finding the Euler totient of $r\n";

        # we'll do a trial division to find the totient
        # there are faster ways that use a sieve
        # but we don't know how big r is
        my $t = $r;

        # by construction p will always be prime when it is used
        # OPEN ISSUE: this might be slow
        for (my $p = 2; $r > 1; $p++) {
            next if $r % $p;

            print "\t$p is a factor\n" if $verbose;
            # decrease the totient
            $t /= $p;
            $t *= $p - 1;

            # decrease r
            $r /= $p; # we know there's at least one factor of p
            $r /= $p until $r % $p; # there might be more
        }

        print "Totient is $t\n";

        return $t;
    }

    sub polypow($$\@) {
        my $n = shift; # this is both the mod and the exponent
        my $r = shift;
        my @base = @{ +shift };

        my $exp = $n;
        my @result = (1); # 1

        # print "\t(", join(" ", @base), ")^$exp mod (x^$r - 1, $n)\n" if $verbose;

        # basic modpow routine, but with polynomials
        while ($exp) {
            if ($exp % 2) {
                @result = polymult($n, $r, @result, @base);
            }

            $exp = int ($exp / 2);
            @base = polymult($n, $r, @base, @base);
        }

        # print "\t= (", join(" ", @result), ")\n" if $verbose;
        return @result;
    }

    sub polymult($$\@\@) {
        my $n = shift;
        my $r = shift;
        my @first = @{ +shift };
        my @second = @{ +shift };

        # print "\t\t(", join(" ", @first), ") * (", join(" ", @second), ") mod (x^$r - 1, $n)\n" if $verbose;

        my @result = ();

        # first do a straight multiplication first * second
        my $s = @second - 1;
        for (my $i = @first - 1; $i >= 0; $i--) {
            for (my $j = $s; $j >= 0; $j--) {
                my $k = $i + $j;
                $result[$k] += $first[$i] * $second[$j];
                $result[$k] %= $n;
            }
        }

        # then do a straight mod x^r - 1
        # consider a polynomial
        # c0 + ... + ck x^k
        # with k >= r
        # we can subtract ck (x^r - 1)
        # without changing the mod value
        # the net effect is to eliminate the x^k term
        # and add ck to the x^(k - r) term

        for (my $i = @result - 1; $i >= $r; $i--) {
            my $j = $i - $r;
            $result[$j] += $result[$i];
            $result[$j] %= $n;

            pop @result;
        }

        # eliminate any leading zero terms
        for (my $i = @result - 1; 0 == $result[$i]; $i--) {
            pop @result;
        }

        # print "\t\t= (", join(" ", @result), ")\n" if $verbose;
        return @result;
    }

    sub polyeq(\@\@) {
        my @lhs = @{ +shift };
        my @rhs = @{ +shift };

        # print "(", join(" ", @lhs), ") = (", join(" ", @rhs), ")?\n" if $verbose;

        return 0 unless @lhs == @rhs;

        for (my $i = @lhs - 1; $i >= 0; $i--) {
            return 0 unless $lhs[$i] == $rhs[$i];
        }

        return 1;
    }

    Here's the output when I run it on 19:

    >perl -w aks.pl 19
    Checking for power-ness...
    Not a power.
    Looking for the first r where o_r(19) > 25...
    r = 19
    Checking GCD(19, a) for a = 2 to 19...
    All GCDs are 1 or 19
    19 >= 19 so 19 is PRIME

    And here's the output with a bigger input:

    >perl -w aks.pl 99
    Checking for power-ness...
    Not a power.
    Looking for the first r where o_r(997) > 100...
    r = 103
    Checking GCD(997, a) for a = 2 to 103...
    All GCDs are 1 or 997
    Finding the Euler totient of 103
    Totient is 102
    Checking polynomials up to roughly 100...
    997 is PRIME
  • Matthew van Eerde's web log

    Excruciating rhymes

    • 0 Comments

    I was watching How the Grinch Stole Christmas and I was struck by this rhyme (from the song  "You're a Mean One, Mr. Grinch:")

    You're a nauseous super naus!
    You're a dirty crooked jockey, and you drive a crooked hoss
       
    -- Dr. Seuss, How the Grinch Stole Christmas

    I tried to see what other particularly excruciating rhymes I could remember.  I came up with two:

    You know, that little guy, he's got me feeling all contempt-ey:
    He takes his boat out loaded up and brings it back in empty.
       
    -- Phil Vischer, Lyle the Kindly Viking

    And then of course:

    In short, when I've a smattering of elemental strategy,
    You'll say a better Major-General had never sat a-gee!
       
    -- W. S. Gilbert, The Pirates of Penzance

Page 2 of 6 (144 items) 12345»