Matthew van Eerde's web log

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

Maurits [MSFT] — Sun, 09 Jun 2013 08:12:00 GMT

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.

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

Maurits [MSFT] — Wed, 13 Mar 2013 17:58:00 GMT

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
...

How to dump Speech API object properties

Maurits [MSFT] — Thu, 22 Nov 2012 00:35:00 GMT

Stamatis Pap asked in a forum thread how to use a Speech API ISpVoice with a non-default audio device. This 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.

Generating sample first names

Maurits [MSFT] — Wed, 24 Oct 2012 20:57:00 GMT

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)

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

Maurits [MSFT] — Thu, 18 Oct 2012 17:51:39 GMT

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.

Changing the desktop wallpaper using IDesktopWallpaper

Maurits [MSFT] — Wed, 10 Oct 2012 13:20:16 GMT

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

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

Maurits [MSFT] — Mon, 01 Oct 2012 16:03:47 GMT

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(n²) 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;
}

Finding the longest substring which occurs twice in a given string

Maurits [MSFT] — Sat, 29 Sep 2012 00:41:00 GMT

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(n²) 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;
}

Enumerating mixer devices, mixer lines, and mixer controls

Maurits [MSFT] — Fri, 28 Sep 2012 01:40:00 GMT

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

Enumerating MIDI devices

Maurits [MSFT] — Fri, 21 Sep 2012 16:31:00 GMT

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.